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 import java.util.Stack;
  12
  13 import IR.Descriptor;
  14 import IR.FieldDescriptor;
  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         // System.out.println("node1=" + node1 + " vs node2=" + node2);
 373         if (!isEligibleForMerging(node1, node2)) {
 374           continue;
 375         }
 376
 377         if (!node1.equals(node2)) {
 378
 379           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
 380           Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
 381
 382           // System.out.println(node1 + " " + node2 + " MERGING incoming?=" + incomingNodeSet1
 383           // + " vs " + incomingNodeSet2);
 384           // System.out.println(node1 + " " + node2 + " MERGING outgoing?=" + outgoingNodeSet1
 385           // + " vs " + outgoingNodeSet2);
 386
 387           if (incomingNodeSet1.equals(incomingNodeSet2)
 388               && outgoingNodeSet1.equals(outgoingNodeSet2)) {
 389             // need to merge node1 and node2
 390             // System.out.println("MERGE!!!!!!!!!!!!!");
 391             // ///////////////
 392             // merge two nodes only if every hierarchy graph in the inheritance hierarchy
 393             // that includes both nodes allows the merging of them...
 394             Set<HNode> mergeSet = new HashSet<HNode>();
 395             mergeSet.add(node1);
 396             mergeSet.add(node2);
 397             infer.isValidMergeInheritanceCheck(desc, mergeSet);
 398
 399             // ///////////////
 400
 401             mergeNodes(mergeSet);
 402             return true;
 403           }
 404
 405         }
 406       }
 407
 408     }
 409     return false;
 410   }
 411
 412   private boolean isEligibleForMerging(HNode node1, HNode node2) {
 413
 414     if (node1.isSharedNode() || node2.isSharedNode()) {
 415
 416       // if either of nodes is a shared node,
 417       // all descriptors of node1 & node2 should have a primitive type
 418
 419       Set<Descriptor> descSet = new HashSet<Descriptor>();
 420       descSet.addAll(getDescSetOfNode(node1));
 421       descSet.addAll(getDescSetOfNode(node2));
 422
 423       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 424         Descriptor desc = (Descriptor) iterator.next();
 425         if (!LocationInference.isPrimitive(desc)) {
 426           return false;
 427         }
 428       }
 429       return true;
 430     }
 431     return true;
 432   }
 433
 434   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
 435     getIncomingNodeSet(dstHNode).add(srcHNode);
 436     getOutgoingNodeSet(srcHNode).add(dstHNode);
 437     // System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
 438   }
 439
 440   private HNode mergeNodes(Set<HNode> set) {
 441
 442     Set<HNode> incomingNodeSet = new HashSet<HNode>();
 443     Set<HNode> outgoingNodeSet = new HashSet<HNode>();
 444
 445     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 446       HNode node = (HNode) iterator.next();
 447       incomingNodeSet.addAll(getIncomingNodeSet(node));
 448       outgoingNodeSet.addAll(getOutgoingNodeSet(node));
 449     }
 450
 451     String nodeName;
 452     boolean isMergeNode = false;
 453     nodeName = "MNode" + (LocationInference.locSeed++);
 454     isMergeNode = true;
 455
 456     HNode newMergeNode = new HNode(nodeName);
 457     newMergeNode.setMergeNode(isMergeNode);
 458
 459     nodeSet.add(newMergeNode);
 460     nodeSet.removeAll(set);
 461
 462     // if the input set contains a skeleton node, need to set a new merge node as skeleton also
 463     boolean hasSkeleton = false;
 464     boolean hasShared = false;
 465     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 466       HNode inNode = (HNode) iterator.next();
 467       if (inNode.isSkeleton()) {
 468         hasSkeleton = true;
 469       }
 470       if (inNode.isSharedNode()) {
 471         hasShared = true;
 472       }
 473     }
 474     // System.out.println("-----Set merging node=" + newMergeNode + " as a skeleton=" + set
 475     // + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
 476     newMergeNode.setSkeleton(hasSkeleton);
 477     newMergeNode.setSharedNode(hasShared);
 478
 479     // System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
 480
 481     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 482       HNode node = (HNode) iterator.next();
 483       Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
 484       for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
 485         Descriptor desc = (Descriptor) iterator2.next();
 486         mappingDescriptorToHNode(desc, newMergeNode);
 487       }
 488     }
 489
 490     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 491       HNode inNode = (HNode) iterator.next();
 492       Set<HNode> outSet = getOutgoingNodeSet(inNode);
 493       outSet.removeAll(set);
 494       if (!set.contains(inNode)) {
 495         addEdgeWithNoCycleCheck(inNode, newMergeNode);
 496       }
 497     }
 498
 499     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 500       HNode outNode = (HNode) iterator.next();
 501       Set<HNode> inSet = getIncomingNodeSet(outNode);
 502       inSet.removeAll(set);
 503       if (!set.contains(outNode)) {
 504         addEdgeWithNoCycleCheck(newMergeNode, outNode);
 505       }
 506     }
 507
 508     Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
 509     for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
 510       HNode merged = iter.next();
 511       if (merged.isSkeleton()) {
 512         mergedSkeletonNode.add(merged);
 513       }
 514     }
 515
 516     // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
 517     // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 518     mapMergeNodetoMergingSet.put(newMergeNode, set);
 519     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 520       HNode mergedNode = (HNode) iterator.next();
 521       addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
 522     }
 523
 524     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 525       HNode hNode = (HNode) iterator.next();
 526       // System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
 527     }
 528
 529     // System.out.println();
 530
 531     return newMergeNode;
 532   }
 533
 534   private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
 535
 536     if (curNode.isMergeNode()) {
 537       Set<HNode> mergingSet = getMergingSet(curNode);
 538       mergingSet.add(curNode);
 539       // System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
 540       // + mergingSet + " newNode=" + newNode);
 541       for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
 542         HNode mergingNode = (HNode) iterator.next();
 543         mapHNodeToCurrentHNode.put(mergingNode, newNode);
 544         mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
 545       }
 546     } else {
 547       mapHNodeToCurrentHNode.put(curNode, newNode);
 548       mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
 549     }
 550
 551   }
 552
 553   public HNode getCurrentHNode(HNode node) {
 554     if (!mapHNodeToCurrentHNode.containsKey(node)) {
 555       mapHNodeToCurrentHNode.put(node, node);
 556     }
 557     return mapHNodeToCurrentHNode.get(node);
 558   }
 559
 560   public HNode getCurrentHNode(String nodeName) {
 561     return mapHNodeNameToCurrentHNode.get(nodeName);
 562   }
 563
 564   private Set<HNode> getMergingSet(HNode mergeNode) {
 565     Set<HNode> mergingSet = new HashSet<HNode>();
 566     Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
 567     for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
 568       HNode node = (HNode) iterator.next();
 569       if (node.isMergeNode()) {
 570         mergingSet.add(node);
 571         mergingSet.addAll(getMergingSet(node));
 572       } else {
 573         mergingSet.add(node);
 574       }
 575     }
 576     return mergingSet;
 577   }
 578
 579   public Set<Descriptor> getDescSetOfNode(HNode node) {
 580     if (!mapHNodeToDescSet.containsKey(node)) {
 581       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 582     }
 583     return mapHNodeToDescSet.get(node);
 584   }
 585
 586   private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
 587     Set<HNode> connectedSet = getOutgoingNodeSet(src);
 588     for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
 589       HNode n = iterator.next();
 590       if (n.equals(dst)) {
 591         return true;
 592       }
 593       if (!visited.contains(n)) {
 594         visited.add(n);
 595         if (reachTo(n, dst, visited)) {
 596           return true;
 597         }
 598       }
 599     }
 600     return false;
 601   }
 602
 603   private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
 604
 605     Set<HNode> outSet = getOutgoingNodeSet(node);
 606     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 607       HNode outNode = (HNode) iterator.next();
 608
 609       if (outNode.isSkeleton()) {
 610         connected.add(outNode);
 611       } else if (!visited.contains(outNode)) {
 612         visited.add(outNode);
 613         recurReachSkeletonSet(outNode, connected, visited);
 614       }
 615     }
 616
 617   }
 618
 619   public Set<HNode> getReachableSCNodeSet(HNode startNode) {
 620     // returns the set of hnodes which is reachable from the startNode and is either SC node or a
 621     // node which is directly connected to the SC nodes
 622     Set<HNode> reachable = new HashSet<HNode>();
 623     Set<HNode> visited = new HashSet<HNode>();
 624     visited.add(startNode);
 625     recurReachableNodeSet(startNode, visited, reachable);
 626     return reachable;
 627   }
 628
 629   public Set<HNode> getSCNodeReachToSet(HNode node) {
 630     if (!mapNormalNodeToSCNodeReachToSet.containsKey(node)) {
 631       mapNormalNodeToSCNodeReachToSet.put(node, new HashSet<HNode>());
 632     }
 633     return mapNormalNodeToSCNodeReachToSet.get(node);
 634   }
 635
 636   private void recurReachableNodeSet(HNode node, Set<HNode> visited, Set<HNode> reachable) {
 637
 638     Set<HNode> outSet = getOutgoingNodeSet(node);
 639     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 640       HNode out = (HNode) iterator.next();
 641
 642       if (!visited.contains(out)) {
 643         visited.add(out);
 644         Set<HNode> reachableFromSCNodeSet = reachableFromSCNode(out);
 645         mapNormalNodeToSCNodeReachToSet.put(out, reachableFromSCNodeSet);
 646         if (out.isSkeleton() || out.isCombinationNode() || reachableFromSCNodeSet.size() > 0) {
 647           reachable.add(out);
 648         } else {
 649           visited.add(out);
 650           recurReachableNodeSet(out, visited, reachable);
 651         }
 652
 653       }
 654
 655     }
 656
 657   }
 658
 659   private Set<HNode> reachableFromSCNode(HNode node) {
 660     Set<HNode> visited = new HashSet<HNode>();
 661     visited.add(node);
 662     Set<HNode> reachable = new HashSet<HNode>();
 663     recurReachableFromSCNode(node, reachable, visited);
 664     return reachable;
 665   }
 666
 667   private void recurReachableFromSCNode(HNode node, Set<HNode> reachable, Set<HNode> visited) {
 668     Set<HNode> inNodeSet = getIncomingNodeSet(node);
 669     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 670       HNode inNode = (HNode) iterator.next();
 671       if (inNode.isSkeleton() || inNode.isCombinationNode()) {
 672         visited.add(inNode);
 673         reachable.add(inNode);
 674       } else if (!visited.contains(inNode)) {
 675         visited.add(inNode);
 676         recurReachableFromSCNode(inNode, reachable, visited);
 677       }
 678     }
 679   }
 680
 681   public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
 682       Set<HNode> combinationNodeSet) {
 683     Set<HNode> reachable = new HashSet<HNode>();
 684     Set<HNode> visited = new HashSet<HNode>();
 685     visited.add(node);
 686     recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
 687     return reachable;
 688   }
 689
 690   public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
 691       Set<HNode> reachable, Set<HNode> combinationNodeSet) {
 692
 693     Set<HNode> outSet = getOutgoingNodeSet(node);
 694     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 695       HNode out = (HNode) iterator.next();
 696
 697       if (!visited.contains(out)) {
 698         visited.add(out);
 699         if (out.isSkeleton()) {
 700           reachable.add(out);
 701         } else if (out.isCombinationNode()) {
 702           if (combinationNodeSet == null) {
 703             reachable.add(out);
 704           } else if (!combinationNodeSet.contains(out)) {
 705             reachable.add(out);
 706           } else {
 707             recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 708                 combinationNodeSet);
 709           }
 710         } else {
 711           recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 712               combinationNodeSet);
 713         }
 714
 715       }
 716
 717     }
 718
 719   }
 720
 721   public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
 722     Set<HNode> visited = new HashSet<HNode>();
 723     return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
 724   }
 725
 726   public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
 727
 728     Set<HNode> outSet = getOutgoingNodeSet(node);
 729     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 730       HNode out = (HNode) iterator.next();
 731       // if (!visited.contains(out)) {
 732       if (out.isCombinationNode() || out.isSkeleton()) {
 733         return out;
 734       } else {
 735         // visited.add(out);
 736         return getDirectlyReachableSkeletonCombinationNodeFrom(out);
 737       }
 738     }
 739     // }
 740
 741     return null;
 742   }
 743
 744   public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
 745     // if an edge from src to dst introduces a new cycle flow,
 746     // the method returns the set of elements consisting of the cycle
 747     Set<HNode> cycleNodeSet = new HashSet<HNode>();
 748     // if the dst node reaches to the src node, the new relation
 749     // introduces a cycle to the lattice
 750     if (dst.equals(src)) {
 751       cycleNodeSet.add(dst);
 752       cycleNodeSet.add(src);
 753     } else if (reachTo(dst, src)) {
 754       cycleNodeSet.add(dst);
 755       cycleNodeSet.add(src);
 756       getInBetweenElements(dst, src, cycleNodeSet);
 757     }
 758     return cycleNodeSet;
 759   }
 760
 761   private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
 762     Set<HNode> connectedSet = getOutgoingNodeSet(start);
 763     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
 764       HNode cur = (HNode) iterator.next();
 765       if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
 766         nodeSet.add(cur);
 767         getInBetweenElements(cur, end, nodeSet);
 768       }
 769     }
 770   }
 771
 772   public boolean reachTo(HNode node1, HNode node2) {
 773     return reachTo(node1, node2, new HashSet<HNode>());
 774   }
 775
 776   public Set<HNode> getCombineSetByCombinationNode(HNode node) {
 777     if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
 778       mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
 779     }
 780     return mapCombinationNodeToCombineNodeSet.get(node);
 781   }
 782
 783   public HNode getCombinationNode(Set<HNode> combineSet) {
 784     assert isSCGraph();
 785     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
 786       String name = "COMB" + (LocationInference.locSeed++);
 787       System.out.println("-NEW COMB NODE=" + name);
 788       HNode node = new HNode(name);
 789       node.setCombinationNode(true);
 790       nodeSet.add(node);
 791       mapCombineNodeSetToCombinationNode.put(combineSet, node);
 792       mapCombinationNodeToCombineNodeSet.put(node, combineSet);
 793     }
 794
 795     return mapCombineNodeSetToCombinationNode.get(combineSet);
 796   }
 797
 798   public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
 799     return mapCombineNodeSetToCombinationNode;
 800   }
 801
 802   public Set<Set<HNode>> getCombineNodeSet() {
 803     return mapCombineNodeSetToOutgoingNodeSet.keySet();
 804   }
 805
 806   public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
 807     // add a new combination node where parameter/field flows are actually combined.
 808
 809     simpleHierarchyGraph.identifyCombinationNodes();
 810
 811     Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
 812     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 813       Set<HNode> combineSet = (Set<HNode>) iterator.next();
 814       HNode combinationNode = getCombinationNode(combineSet);
 815       System.out.println("\n@INSERT COMBINATION NODE FOR combineSet=" + combineSet
 816           + "  --combinationNode=" + combinationNode);
 817       System.out.println("      --hierarchynodes="
 818           + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
 819
 820       Set<HNode> simpleHNodeSet =
 821           simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet);
 822
 823       // check whether a hnode in the simple hierarchy graph is the first node of the chain
 824       // if all incoming combination nodes to the hnode have a different combination set from the
 825       // hnode, it is the first node of the chain
 826       for (Iterator iterator2 = simpleHNodeSet.iterator(); iterator2.hasNext();) {
 827         HNode simpleHNode = (HNode) iterator2.next();
 828         boolean isFirstNodeOfChain = true;
 829         Set<HNode> incomingNodeSet = simpleHierarchyGraph.getIncomingNodeSet(simpleHNode);
 830         for (Iterator iterator3 = incomingNodeSet.iterator(); iterator3.hasNext();) {
 831           HNode inNode = (HNode) iterator3.next();
 832           if (inNode.isCombinationNode()) {
 833             Set<HNode> inNodeCombineSet =
 834                 simpleHierarchyGraph.getCombineSetByCombinationNode(inNode);
 835             if (inNodeCombineSet.equals(combineSet)) {
 836               isFirstNodeOfChain = false;
 837               break;
 838             }
 839           }
 840         }
 841         simpleHNode.setDirectCombinationNode(isFirstNodeOfChain);
 842         if (isFirstNodeOfChain) {
 843           simpleHierarchyGraph.addFirstNodeOfChain(combineSet, simpleHNode);
 844           System.out.println("IT IS THE FIRST NODE OF THE CHAIN:" + simpleHNode);
 845           // System.out.println("--->INCOMING NODES=");
 846           // Set<HNode> inNodeSet = simpleHierarchyGraph.getIncomingNodeSet(simpleHNode);
 847           // for (Iterator iterator3 = inNodeSet.iterator(); iterator3.hasNext();) {
 848           // HNode inNode = (HNode) iterator3.next();
 849           // System.out.println("          inNode=" + inNode + "   combineSet="
 850           // + simpleHierarchyGraph.getCombineSetByCombinationNode(inNode) + " SKELETON TO SET="
 851           // + simpleHierarchyGraph.getSkeleteNodeSetReachTo(inNode));
 852           // }
 853         }
 854       }
 855
 856       // add an edge from a skeleton node to a combination node
 857       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
 858         HNode inSkeletonNode = (HNode) iterator2.next();
 859         // System.out.println("--inSkeletonNode=" + inSkeletonNode + "  desc="
 860         // + inSkeletonNode.getDescriptor());
 861         HNode srcNode;
 862         if (inSkeletonNode.getDescriptor() == null) {
 863           // the node is merging one...
 864           srcNode = inSkeletonNode;
 865         } else {
 866           srcNode = getHNode(inSkeletonNode.getDescriptor());
 867         }
 868         // System.out.println("--srcNode=" + srcNode);
 869         System.out.println("     ADD EDGE SRC=" + srcNode + " -> " + combinationNode);
 870         addEdgeWithNoCycleCheck(srcNode, combinationNode);
 871       }
 872
 873       // add an edge from the combination node to outgoing nodes
 874       Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
 875       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 876         HNode curNode = (HNode) iterator2.next();
 877         if (curNode.isCombinationNode()) {
 878           Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
 879           HNode outNode = getCombinationNode(combineNode);
 880           addEdgeWithNoCycleCheck(combinationNode, outNode);
 881         } else if (curNode.isSkeleton()) {
 882           // HNode dstNode2 = getHNode(curNode.getDescriptor());
 883           HNode dstNode = getCurrentHNode(curNode);
 884           // System.out.println("-----curNode=" + curNode + "------->" + dstNode + "    dstNode2="
 885           // + dstNode2);
 886           addEdgeWithNoCycleCheck(combinationNode, dstNode);
 887         }
 888       }
 889
 890       // System.out.println("--");
 891
 892     }
 893
 894   }
 895
 896   public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 897
 898     Set<HNode> reachToSet = new HashSet<HNode>();
 899     Set<HNode> visited = new HashSet<HNode>();
 900     // visited.add(node);
 901     recurSkeletonReachTo(node, reachToSet, visited);
 902
 903     // obsolete!
 904     // if a node reaches to one of elements in the reachToSet, we do not need to keep it
 905     // because the node is not directly connected to the combination node
 906     // removeRedundantReachToNodes(reachToSet);
 907
 908     return removeTransitivelyReachToSet(reachToSet);
 909     // return reachToSet;
 910   }
 911
 912   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 913
 914     Set<HNode> inSet = getIncomingNodeSet(node);
 915     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 916       HNode inNode = (HNode) iterator.next();
 917
 918       if (inNode.isSkeleton()) {
 919         visited.add(inNode);
 920         reachToSet.add(inNode);
 921       } else if (!visited.contains(inNode)) {
 922         visited.add(inNode);
 923         recurSkeletonReachTo(inNode, reachToSet, visited);
 924       }
 925     }
 926
 927   }
 928
 929   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 930     return mapHNodeToOutgoingSet;
 931   }
 932
 933   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 934     return mapHNodeToIncomingSet;
 935   }
 936
 937   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 938     mapHNodeToOutgoingSet.clear();
 939     Set<HNode> keySet = in.keySet();
 940     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 941       HNode key = (HNode) iterator.next();
 942       Set<HNode> inSet = in.get(key);
 943       Set<HNode> newSet = new HashSet<HNode>();
 944       newSet.addAll(inSet);
 945       mapHNodeToOutgoingSet.put(key, newSet);
 946     }
 947   }
 948
 949   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 950     mapHNodeToIncomingSet.clear();
 951     Set<HNode> keySet = in.keySet();
 952     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 953       HNode key = (HNode) iterator.next();
 954       Set<HNode> inSet = in.get(key);
 955       Set<HNode> newSet = new HashSet<HNode>();
 956       newSet.addAll(inSet);
 957       mapHNodeToIncomingSet.put(key, newSet);
 958     }
 959   }
 960
 961   public void setNodeSet(Set<HNode> inSet) {
 962     nodeSet.clear();
 963     nodeSet.addAll(inSet);
 964   }
 965
 966   public HierarchyGraph clone() {
 967     HierarchyGraph clone = new HierarchyGraph();
 968     clone.setDesc(getDesc());
 969     clone.setName(getName());
 970     clone.setNodeSet(getNodeSet());
 971     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 972     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 973     clone.setMapDescToHNode(getMapDescToHNode());
 974     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 975     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 976     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 977     clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
 978
 979     return clone;
 980   }
 981
 982   public void setMapCombineNodeSetToCombinationNode(Map<Set<HNode>, HNode> in) {
 983     mapCombineNodeSetToCombinationNode = in;
 984   }
 985
 986   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
 987     return mapMergeNodetoMergingSet;
 988   }
 989
 990   public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
 991     this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
 992   }
 993
 994   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
 995
 996     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 997       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 998     }
 999     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
1000   }
1001
1002   public void identifyCombinationNodes() {
1003
1004     // 1) set combination node flag if a node combines more than one skeleton node.
1005     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1006       HNode node = (HNode) iterator.next();
1007       if (!node.isSkeleton()) {
1008         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
1009         // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
1010         // System.out.println("ALL REACH SET=" + reachToSet);
1011         // reachToSet = removeTransitivelyReachToSet(reachToSet);
1012
1013         Set<HNode> curReachToSet = new HashSet<HNode>();
1014         for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
1015           HNode reachSkeletonNode = (HNode) iterator2.next();
1016           curReachToSet.add(getCurrentHNode(reachSkeletonNode));
1017         }
1018
1019         // System.out.println("-curReachToSett=" + curReachToSet + "  reachToSet=" + reachToSet);
1020
1021         reachToSet = curReachToSet;
1022         // System.out.println("$node=" + node + "   reachToNodeSet=" + reachToSet + " tempSet="
1023         // + tempSet);
1024         if (reachToSet.size() > 1) {
1025           // if (countSkeletonNodes(reachToSet) > 1) {
1026           System.out.println("\n-node=" + node + "  reachToSet=" + reachToSet);
1027           System.out.println("-set combinationnode=" + node);
1028           node.setCombinationNode(true);
1029           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
1030
1031           // check if this node is the first node of the chain
1032           // boolean isFirstNodeOfChain = false;
1033           // Set<HNode> inNodeSet = getIncomingNodeSet(node);
1034           // for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
1035           // HNode inNode = (HNode) iterator2.next();
1036           // if (inNode.isSkeleton()) {
1037           // isFirstNodeOfChain = true;
1038           // } else if (inNode.isCombinationNode()) {
1039           // Set<HNode> inNodeReachToSet = getSkeleteNodeSetReachTo(inNode);
1040           // if (!reachToSet.equals(inNodeReachToSet)) {
1041           // isFirstNodeOfChain = true;
1042           // }
1043           // }
1044           // }
1045           //
1046           // if (isFirstNodeOfChain) {
1047           // node.setDirectCombinationNode(true);
1048           // addFirstNodeOfChain(reachToSet, node);
1049           // }
1050
1051         }
1052       }
1053     }
1054
1055     // 2) compute the outgoing set that needs to be directly connected from the combination node
1056     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1057       HNode node = (HNode) iterator.next();
1058       if (node.isCombinationNode()) {
1059         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1060         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
1061         addMapCombineSetToOutgoingSet(combineSet, outSet);
1062       }
1063     }
1064
1065   }
1066
1067   public void addFirstNodeOfChain(Set<HNode> combineSet, HNode firstNode) {
1068
1069     if (!mapCombineNodeSetToFirstNodeOfChainSet.containsKey(combineSet)) {
1070       mapCombineNodeSetToFirstNodeOfChainSet.put(combineSet, new HashSet<HNode>());
1071     }
1072
1073     mapCombineNodeSetToFirstNodeOfChainSet.get(combineSet).add(firstNode);
1074
1075   }
1076
1077   public Set<HNode> getFirstNodeOfCombinationNodeChainSet(Set<HNode> combineNodeSet) {
1078     return mapCombineNodeSetToFirstNodeOfChainSet.get(combineNodeSet);
1079   }
1080
1081   private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
1082
1083     Set<HNode> toberemoved = new HashSet<HNode>();
1084     Set<HNode> visited = new HashSet<HNode>();
1085     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
1086       HNode node = (HNode) iterator.next();
1087       visited.add(node);
1088       recurIsReachingTo(node, reachToSet, toberemoved, visited);
1089     }
1090
1091     Set<HNode> rSet = new HashSet<HNode>();
1092     rSet.addAll(reachToSet);
1093     rSet.removeAll(toberemoved);
1094     return rSet;
1095   }
1096
1097   private void recurIsReachingTo(HNode curNode, Set<HNode> reachToSet, Set<HNode> toberemoved,
1098       Set<HNode> visited) {
1099     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1100
1101     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1102       HNode inNode = (HNode) iterator.next();
1103       if (reachToSet.contains(inNode)) {
1104         toberemoved.add(inNode);
1105       } else if (!visited.contains(inNode)) {
1106         visited.add(inNode);
1107         recurIsReachingTo(inNode, reachToSet, toberemoved, visited);
1108       }
1109     }
1110
1111   }
1112
1113   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
1114     return mapCombinationNodeToCombineNodeSet;
1115   }
1116
1117   public int countSkeletonNodes(Set<HNode> set) {
1118     int count = 0;
1119
1120     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1121       HNode node = (HNode) iterator.next();
1122       Set<Descriptor> descSet = getDescSetOfNode(node);
1123       count += descSet.size();
1124     }
1125
1126     return count;
1127   }
1128
1129   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
1130     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1131       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1132     }
1133     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
1134   }
1135
1136   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
1137     // the method returns the set of nodes that are reachable from the current node
1138     // and do not combine the same set of skeleton nodes...
1139
1140     Set<HNode> visited = new HashSet<HNode>();
1141     Set<HNode> reachableSet = new HashSet<HNode>();
1142     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1143
1144     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
1145
1146     return reachableSet;
1147   }
1148
1149   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
1150       Set<HNode> reachableSet, Set<HNode> visited) {
1151
1152     Set<HNode> outSet = getOutgoingNodeSet(node);
1153     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1154       HNode outNode = (HNode) iterator.next();
1155
1156       if (outNode.isCombinationNode()) {
1157         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
1158         if (combineSetOfOutNode.equals(combineSet)) {
1159           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
1160               visited);
1161         } else {
1162           reachableSet.add(outNode);
1163         }
1164       } else if (outNode.isSkeleton()) {
1165         reachableSet.add(outNode);
1166       }
1167
1168     }
1169
1170   }
1171
1172   private Set<HNode> getReachableNodeSetFrom(HNode node) {
1173
1174     Set<HNode> reachableSet = new HashSet<HNode>();
1175     Set<HNode> visited = new HashSet<HNode>();
1176
1177     recurReachableNodeSetFrom(node, reachableSet, visited);
1178
1179     return reachableSet;
1180   }
1181
1182   private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
1183
1184     Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
1185     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
1186       HNode outNode = (HNode) iterator.next();
1187       reachableSet.add(outNode);
1188       if (!visited.contains(outNode)) {
1189         visited.add(outNode);
1190         recurReachableNodeSetFrom(outNode, reachableSet, visited);
1191       }
1192     }
1193
1194   }
1195
1196   public void assignUniqueIndexToNode() {
1197     int idx = 1;
1198     // System.out.println("nodeSet=" + nodeSet);
1199     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1200       HNode node = (HNode) iterator.next();
1201       mapHNodeToUniqueIndex.put(node, idx);
1202       idx++;
1203     }
1204
1205     BASISTOPELEMENT = new HashSet<Integer>();
1206     for (int i = 1; i < idx + 1; i++) {
1207       BASISTOPELEMENT.add(i);
1208     }
1209   }
1210
1211   public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1212
1213     // assign a unique index to a node
1214     assignUniqueIndexToNode();
1215
1216     // compute basis for each node
1217     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1218       HNode node = (HNode) iterator.next();
1219
1220       if (notGenerateSet.contains(node)) {
1221         System.out.println("%%%SKIP =" + node);
1222         continue;
1223       }
1224       Set<Integer> basis = new HashSet<Integer>();
1225       basis.addAll(BASISTOPELEMENT);
1226
1227       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1228       // System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
1229       // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1230       // if a node is reachable from the current node
1231       // need to remove the index of the reachable node from the basis
1232
1233       basis.remove(getHNodeIndex(node));
1234       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1235         HNode reachableNode = (HNode) iterator2.next();
1236         // System.out.println("reachableNode=" + reachableNode);
1237         // System.out.println("getHNodeIndex(reachableNode))="
1238         // + mapHNodeToUniqueIndex.get(reachableNode));
1239         int idx = getHNodeIndex(reachableNode);
1240         basis.remove(idx);
1241       }
1242
1243       mapHNodeToBasis.put(node, basis);
1244     }
1245
1246     // construct the basis set
1247
1248     BasisSet basisSet = new BasisSet();
1249
1250     Set<HNode> keySet = mapHNodeToBasis.keySet();
1251     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1252       HNode node = (HNode) iterator.next();
1253       Set<Integer> basis = mapHNodeToBasis.get(node);
1254       basisSet.addElement(basis, node);
1255     }
1256
1257     return basisSet;
1258
1259   }
1260
1261   public int getHNodeIndex(HNode node) {
1262     return mapHNodeToUniqueIndex.get(node).intValue();
1263   }
1264
1265   public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1266     return mapHNodeToUniqueIndex;
1267   }
1268
1269   public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1270     return mapHNodeToBasis;
1271   }
1272
1273   public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1274
1275     Set<HNode> combinationNodeSet = new HashSet<HNode>();
1276     Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1277     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1278       HNode key = (HNode) iterator.next();
1279
1280       if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1281         combinationNodeSet.add(key);
1282       }
1283     }
1284
1285     return combinationNodeSet;
1286   }
1287
1288   public void writeGraph() {
1289     writeGraph(false);
1290   }
1291
1292   public void writeGraph(boolean isSimple) {
1293
1294     String graphName = "hierarchy" + name;
1295     graphName = graphName.replaceAll("[\\W]", "");
1296
1297     if (isSimple) {
1298       graphName += "_PAPER";
1299     }
1300
1301     // System.out.println("***graphName=" + graphName + "   node siz=" + nodeSet.size());
1302
1303     try {
1304       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1305
1306       bw.write("digraph " + graphName + " {\n");
1307
1308       Iterator<HNode> iter = nodeSet.iterator();
1309
1310       Set<HNode> addedNodeSet = new HashSet<HNode>();
1311
1312       while (iter.hasNext()) {
1313         HNode u = iter.next();
1314
1315         Set<HNode> outSet = getOutgoingNodeSet(u);
1316
1317         if (outSet.size() == 0) {
1318           if (!addedNodeSet.contains(u)) {
1319             if (!isSimple) {
1320               drawNode(bw, u);
1321             } else {
1322               drawNodeName(bw, u);
1323             }
1324             addedNodeSet.add(u);
1325           }
1326         } else {
1327           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1328             HNode v = (HNode) iterator.next();
1329             if (!addedNodeSet.contains(u)) {
1330               if (!isSimple) {
1331                 drawNode(bw, u);
1332               } else {
1333                 drawNodeName(bw, u);
1334               }
1335               addedNodeSet.add(u);
1336             }
1337             if (!addedNodeSet.contains(v)) {
1338               if (!isSimple) {
1339                 drawNode(bw, v);
1340               } else {
1341                 drawNodeName(bw, v);
1342               }
1343               addedNodeSet.add(v);
1344             }
1345             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1346           }
1347         }
1348
1349       }
1350
1351       bw.write("}\n");
1352       bw.close();
1353
1354     } catch (IOException e) {
1355       e.printStackTrace();
1356     }
1357   }
1358
1359   public boolean contains(HNode node) {
1360     return nodeSet.contains(node);
1361   }
1362
1363   public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1364     return getOutgoingNodeSet(src).contains(dst);
1365   }
1366
1367   private String convertMergeSetToString(Set<HNode> mergeSet) {
1368     String str = "";
1369     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1370       HNode merged = (HNode) iterator.next();
1371       if (merged.isMergeNode()) {
1372         str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1373       } else {
1374         str += " " + merged.getName();
1375       }
1376     }
1377     return str;
1378   }
1379
1380   private void drawNodeName(BufferedWriter bw, HNode node) throws IOException {
1381     String nodeName = node.getNamePropertyString();
1382     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1383   }
1384
1385   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1386     String nodeName;
1387     if (node.isMergeNode()) {
1388       nodeName = node.getNamePropertyString();
1389       Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1390       // System.out.println("node=" + node + "   mergeSet=" + mergeSet);
1391       nodeName += ":" + convertMergeSetToString(mergeSet);
1392     } else {
1393       nodeName = node.getNamePropertyString();
1394     }
1395     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1396   }
1397
1398   public int countHopFromTopLocation(HNode node) {
1399
1400     Set<HNode> inNodeSet = getIncomingNodeSet(node);
1401     int count = 0;
1402     if (inNodeSet.size() > 0) {
1403       count = recurCountHopFromTopLocation(inNodeSet, 1);
1404     }
1405
1406     return count;
1407   }
1408
1409   private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1410
1411     int max = curCount;
1412     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1413       HNode node = (HNode) iterator.next();
1414       Set<HNode> inNodeSet = getIncomingNodeSet(node);
1415       if (inNodeSet.size() > 0) {
1416         int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1417         if (max < recurCount) {
1418           max = recurCount;
1419         }
1420       }
1421     }
1422     return max;
1423   }
1424
1425   public Stack<String> computeDistance(HNode startNode, Set<HNode> endNodeSet, Set<HNode> combineSet) {
1426     // System.out.println("#####computeDistanceance startNode=" + startNode + " endNode=" +
1427     // endNodeSet);
1428     Stack<String> trace = new Stack<String>();
1429     return recur_computeDistance(startNode, endNodeSet, 0, combineSet, trace);
1430   }
1431
1432   private Stack<String> recur_computeDistance(HNode curNode, Set<HNode> endNodeSet, int count,
1433       Set<HNode> combineSet, Stack<String> trace) {
1434
1435     if (!curNode.isSkeleton()) {
1436       if (curNode.isSharedNode()) {
1437         trace.add("S");
1438       } else {
1439         trace.add("N");
1440       }
1441     }
1442
1443     if (endNodeSet.contains(curNode)) {
1444       // it reaches to one of endNodeSet
1445       return trace;
1446     }
1447
1448     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1449
1450     int curMaxDistance = 0;
1451     Stack<String> curMaxTrace = (Stack<String>) trace.clone();
1452     ;
1453     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1454       HNode inNode = (HNode) iterator.next();
1455       // traverse more...
1456
1457       if (inNode.isCombinationNode() && combineSet != null) {
1458         // check if inNode have the same combination set of the starting node
1459         Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
1460         if (!inNodeCombineSet.equals(combineSet)) {
1461           continue;
1462         }
1463       }
1464
1465       // System.out.println("    traverse more to" + inNode + "  before-trace=" + trace);
1466       Stack<String> newTrace = (Stack<String>) trace.clone();
1467       Stack<String> curTrace =
1468           recur_computeDistance(inNode, endNodeSet, count, combineSet, newTrace);
1469       // System.out.println("curTracerTrace=" + curTrace);
1470
1471       if (curTrace != null && curTrace.size() > curMaxDistance) {
1472         curMaxTrace = curTrace;
1473         curMaxDistance = curTrace.size();
1474       }
1475     }
1476     return curMaxTrace;
1477   }
1478
1479   private int recur_computeDistance2(HNode startNode, HNode curNode, Set<HNode> endNodeSet,
1480       int count, Set<HNode> combineSet) {
1481
1482     if (!curNode.equals(startNode)) {
1483       // do not count the start node
1484       count++;
1485     }
1486
1487     if (endNodeSet.contains(curNode)) {
1488       // it reaches to one of endNodeSet
1489       return count;
1490     }
1491
1492     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1493
1494     int curMaxDistance = 0;
1495     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1496       HNode inNode = (HNode) iterator.next();
1497       // traverse more...
1498
1499       if (inNode.isCombinationNode() && combineSet != null) {
1500         // check if inNode have the same combination set of the starting node
1501         Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
1502         if (!inNodeCombineSet.equals(combineSet)) {
1503           continue;
1504         }
1505       }
1506
1507       System.out.println("    traverse more to" + inNode + "  before-count=" + count);
1508       int dist = recur_computeDistance2(startNode, inNode, endNodeSet, count, combineSet);
1509       if (dist > curMaxDistance) {
1510         curMaxDistance = dist;
1511       }
1512     }
1513     return curMaxDistance;
1514   }
1515
1516   public int computeDistance2(HNode startNode, Set<HNode> endNodeSet, Set<HNode> combineSet) {
1517     System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet);
1518     return recur_computeDistance2(startNode, startNode, endNodeSet, 0, 0, combineSet);
1519   }
1520
1521   private int recur_computeDistance2(HNode startNode, HNode curNode, Set<HNode> endNodeSet,
1522       int sharedCount, int nonSharedCount, Set<HNode> combineSet) {
1523
1524     if (!curNode.equals(startNode)) {
1525       // do not count the start node
1526       if (curNode.isSharedNode()) {
1527         sharedCount++;
1528       } else {
1529         nonSharedCount++;
1530       }
1531     }
1532
1533     if (endNodeSet.contains(curNode)) {
1534       // it reaches to one of endNodeSet
1535       if (sharedCount > nonSharedCount) {
1536         return sharedCount;
1537       } else {
1538         return nonSharedCount;
1539       }
1540     }
1541
1542     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1543
1544     int curMaxDistance = 0;
1545     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1546       HNode inNode = (HNode) iterator.next();
1547       // traverse more...
1548
1549       if (inNode.isCombinationNode() && combineSet != null) {
1550         // check if inNode have the same combination set of the starting node
1551         Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
1552         if (!inNodeCombineSet.equals(combineSet)) {
1553           continue;
1554         }
1555       }
1556
1557       System.out.println("    traverse more to" + inNode + "  sC=" + sharedCount + " nC="
1558           + nonSharedCount);
1559       int dist =
1560           recur_computeDistance2(startNode, inNode, endNodeSet, sharedCount, nonSharedCount,
1561               combineSet);
1562       if (dist > curMaxDistance) {
1563         curMaxDistance = dist;
1564       }
1565     }
1566     return curMaxDistance;
1567   }
1568
1569   public int countNonSharedNode(HNode startNode, Set<HNode> endNodeSet) {
1570     System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
1571     return recur_countNonSharedNode(startNode, endNodeSet, 0);
1572   }
1573
1574   private int recur_countNonSharedNode(HNode startNode, Set<HNode> endNodeSet, int count) {
1575
1576     Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
1577
1578     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1579       HNode inNode = (HNode) iterator.next();
1580       if (endNodeSet.contains(inNode)) {
1581         count++;
1582         return count;
1583       } else {
1584         if (!inNode.isSharedNode()) {
1585           count++;
1586         }
1587         return recur_countNonSharedNode2(inNode, endNodeSet, count);
1588       }
1589     }
1590
1591     return 0;
1592   }
1593
1594   public int countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet) {
1595     System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
1596     return recur_countNonSharedNode2(startNode, endNodeSet, 0);
1597   }
1598
1599   private int recur_countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet, int count) {
1600
1601     Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
1602
1603     if (inNodeSet.size() == 0) {
1604       // it is directly connected to the TOP node
1605     }
1606
1607     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1608       HNode inNode = (HNode) iterator.next();
1609       if (endNodeSet.contains(inNode)) {
1610         return count;
1611       } else {
1612         if (!inNode.isSharedNode()) {
1613           count++;
1614         }
1615         return recur_countNonSharedNode2(inNode, endNodeSet, count);
1616       }
1617     }
1618
1619     // System.out.println("startNode=" + startNode + " inNodeSet=" + inNodeSet);
1620     // HNode inNode = inNodeSet.iterator().next();
1621     return -1;
1622   }
1623
1624   public void removeIsolatedNodes() {
1625     Set<HNode> toberemoved = new HashSet<HNode>();
1626     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1627       HNode node = (HNode) iterator.next();
1628       if (getIncomingNodeSet(node).isEmpty() && getOutgoingNodeSet(node).isEmpty()) {
1629         toberemoved.add(node);
1630       }
1631     }
1632     nodeSet.removeAll(toberemoved);
1633   }
1634 }