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> getSkeleteNodeSetReachToNoTransitive(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   public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 913
 914     Set<HNode> reachToSet = new HashSet<HNode>();
 915     Set<HNode> visited = new HashSet<HNode>();
 916     // visited.add(node);
 917     recurSkeletonReachTo(node, reachToSet, visited);
 918
 919     // obsolete!
 920     // if a node reaches to one of elements in the reachToSet, we do not need to keep it
 921     // because the node is not directly connected to the combination node
 922     // removeRedundantReachToNodes(reachToSet);
 923
 924     // TODO
 925     return removeTransitivelyReachToSet(reachToSet);
 926     // return reachToSet;
 927   }
 928
 929   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 930
 931     Set<HNode> inSet = getIncomingNodeSet(node);
 932     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 933       HNode inNode = (HNode) iterator.next();
 934
 935       if (inNode.isSkeleton()) {
 936         visited.add(inNode);
 937         reachToSet.add(inNode);
 938       } else if (!visited.contains(inNode)) {
 939         visited.add(inNode);
 940         recurSkeletonReachTo(inNode, reachToSet, visited);
 941       }
 942     }
 943
 944   }
 945
 946   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 947     return mapHNodeToOutgoingSet;
 948   }
 949
 950   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 951     return mapHNodeToIncomingSet;
 952   }
 953
 954   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 955     mapHNodeToOutgoingSet.clear();
 956     Set<HNode> keySet = in.keySet();
 957     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 958       HNode key = (HNode) iterator.next();
 959       Set<HNode> inSet = in.get(key);
 960       Set<HNode> newSet = new HashSet<HNode>();
 961       newSet.addAll(inSet);
 962       mapHNodeToOutgoingSet.put(key, newSet);
 963     }
 964   }
 965
 966   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 967     mapHNodeToIncomingSet.clear();
 968     Set<HNode> keySet = in.keySet();
 969     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 970       HNode key = (HNode) iterator.next();
 971       Set<HNode> inSet = in.get(key);
 972       Set<HNode> newSet = new HashSet<HNode>();
 973       newSet.addAll(inSet);
 974       mapHNodeToIncomingSet.put(key, newSet);
 975     }
 976   }
 977
 978   public void setNodeSet(Set<HNode> inSet) {
 979     nodeSet.clear();
 980     nodeSet.addAll(inSet);
 981   }
 982
 983   public HierarchyGraph clone() {
 984     HierarchyGraph clone = new HierarchyGraph();
 985     clone.setDesc(getDesc());
 986     clone.setName(getName());
 987     clone.setNodeSet(getNodeSet());
 988     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 989     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 990     clone.setMapDescToHNode(getMapDescToHNode());
 991     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 992     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 993     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 994     clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
 995
 996     return clone;
 997   }
 998
 999   public void setMapCombineNodeSetToCombinationNode(Map<Set<HNode>, HNode> in) {
1000     mapCombineNodeSetToCombinationNode = in;
1001   }
1002
1003   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
1004     return mapMergeNodetoMergingSet;
1005   }
1006
1007   public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
1008     this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
1009   }
1010
1011   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
1012
1013     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1014       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1015     }
1016     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
1017   }
1018
1019   public void identifyCombinationNodes() {
1020
1021     // 1) set combination node flag if a node combines more than one skeleton node.
1022     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1023       HNode node = (HNode) iterator.next();
1024       if (!node.isSkeleton()) {
1025         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
1026         // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
1027         // System.out.println("ALL REACH SET=" + reachToSet);
1028         // reachToSet = removeTransitivelyReachToSet(reachToSet);
1029
1030         Set<HNode> curReachToSet = new HashSet<HNode>();
1031         for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
1032           HNode reachSkeletonNode = (HNode) iterator2.next();
1033           curReachToSet.add(getCurrentHNode(reachSkeletonNode));
1034         }
1035
1036         // System.out.println("-curReachToSett=" + curReachToSet + "  reachToSet=" + reachToSet);
1037
1038         reachToSet = curReachToSet;
1039         // System.out.println("$node=" + node + "   reachToNodeSet=" + reachToSet + " tempSet="
1040         // + tempSet);
1041         if (reachToSet.size() > 1) {
1042           // if (countSkeletonNodes(reachToSet) > 1) {
1043           System.out.println("\n-node=" + node + "  reachToSet=" + reachToSet);
1044           System.out.println("-set combinationnode=" + node);
1045           node.setCombinationNode(true);
1046           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
1047
1048           // check if this node is the first node of the chain
1049           // boolean isFirstNodeOfChain = false;
1050           // Set<HNode> inNodeSet = getIncomingNodeSet(node);
1051           // for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
1052           // HNode inNode = (HNode) iterator2.next();
1053           // if (inNode.isSkeleton()) {
1054           // isFirstNodeOfChain = true;
1055           // } else if (inNode.isCombinationNode()) {
1056           // Set<HNode> inNodeReachToSet = getSkeleteNodeSetReachTo(inNode);
1057           // if (!reachToSet.equals(inNodeReachToSet)) {
1058           // isFirstNodeOfChain = true;
1059           // }
1060           // }
1061           // }
1062           //
1063           // if (isFirstNodeOfChain) {
1064           // node.setDirectCombinationNode(true);
1065           // addFirstNodeOfChain(reachToSet, node);
1066           // }
1067
1068         }
1069       }
1070     }
1071
1072     // 2) compute the outgoing set that needs to be directly connected from the combination node
1073     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1074       HNode node = (HNode) iterator.next();
1075       if (node.isCombinationNode()) {
1076         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1077         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
1078         addMapCombineSetToOutgoingSet(combineSet, outSet);
1079       }
1080     }
1081
1082   }
1083
1084   public void addFirstNodeOfChain(Set<HNode> combineSet, HNode firstNode) {
1085
1086     if (!mapCombineNodeSetToFirstNodeOfChainSet.containsKey(combineSet)) {
1087       mapCombineNodeSetToFirstNodeOfChainSet.put(combineSet, new HashSet<HNode>());
1088     }
1089
1090     mapCombineNodeSetToFirstNodeOfChainSet.get(combineSet).add(firstNode);
1091
1092   }
1093
1094   public Set<HNode> getFirstNodeOfCombinationNodeChainSet(Set<HNode> combineNodeSet) {
1095     return mapCombineNodeSetToFirstNodeOfChainSet.get(combineNodeSet);
1096   }
1097
1098   private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
1099
1100     Set<HNode> toberemoved = new HashSet<HNode>();
1101     Set<HNode> visited = new HashSet<HNode>();
1102     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
1103       HNode node = (HNode) iterator.next();
1104       visited.add(node);
1105       recurIsReachingTo(node, reachToSet, toberemoved, visited);
1106     }
1107
1108     Set<HNode> rSet = new HashSet<HNode>();
1109     rSet.addAll(reachToSet);
1110     rSet.removeAll(toberemoved);
1111     return rSet;
1112   }
1113
1114   private void recurIsReachingTo(HNode curNode, Set<HNode> reachToSet, Set<HNode> toberemoved,
1115       Set<HNode> visited) {
1116     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1117
1118     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1119       HNode inNode = (HNode) iterator.next();
1120       if (reachToSet.contains(inNode)) {
1121         toberemoved.add(inNode);
1122       } else if (!visited.contains(inNode)) {
1123         visited.add(inNode);
1124         recurIsReachingTo(inNode, reachToSet, toberemoved, visited);
1125       }
1126     }
1127
1128   }
1129
1130   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
1131     return mapCombinationNodeToCombineNodeSet;
1132   }
1133
1134   public int countSkeletonNodes(Set<HNode> set) {
1135     int count = 0;
1136
1137     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1138       HNode node = (HNode) iterator.next();
1139       Set<Descriptor> descSet = getDescSetOfNode(node);
1140       count += descSet.size();
1141     }
1142
1143     return count;
1144   }
1145
1146   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
1147     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1148       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1149     }
1150     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
1151   }
1152
1153   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
1154     // the method returns the set of nodes that are reachable from the current node
1155     // and do not combine the same set of skeleton nodes...
1156
1157     Set<HNode> visited = new HashSet<HNode>();
1158     Set<HNode> reachableSet = new HashSet<HNode>();
1159     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1160
1161     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
1162
1163     return reachableSet;
1164   }
1165
1166   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
1167       Set<HNode> reachableSet, Set<HNode> visited) {
1168
1169     Set<HNode> outSet = getOutgoingNodeSet(node);
1170     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1171       HNode outNode = (HNode) iterator.next();
1172
1173       if (outNode.isCombinationNode()) {
1174         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
1175         if (combineSetOfOutNode.equals(combineSet)) {
1176           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
1177               visited);
1178         } else {
1179           reachableSet.add(outNode);
1180         }
1181       } else if (outNode.isSkeleton()) {
1182         reachableSet.add(outNode);
1183       }
1184
1185     }
1186
1187   }
1188
1189   private Set<HNode> getReachableNodeSetFrom(HNode node) {
1190
1191     Set<HNode> reachableSet = new HashSet<HNode>();
1192     Set<HNode> visited = new HashSet<HNode>();
1193
1194     recurReachableNodeSetFrom(node, reachableSet, visited);
1195
1196     return reachableSet;
1197   }
1198
1199   private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
1200
1201     Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
1202     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
1203       HNode outNode = (HNode) iterator.next();
1204       reachableSet.add(outNode);
1205       if (!visited.contains(outNode)) {
1206         visited.add(outNode);
1207         recurReachableNodeSetFrom(outNode, reachableSet, visited);
1208       }
1209     }
1210
1211   }
1212
1213   public void assignUniqueIndexToNode() {
1214     int idx = 1;
1215     // System.out.println("nodeSet=" + nodeSet);
1216     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1217       HNode node = (HNode) iterator.next();
1218       mapHNodeToUniqueIndex.put(node, idx);
1219       idx++;
1220     }
1221
1222     BASISTOPELEMENT = new HashSet<Integer>();
1223     for (int i = 1; i < idx + 1; i++) {
1224       BASISTOPELEMENT.add(i);
1225     }
1226   }
1227
1228   public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1229
1230     // assign a unique index to a node
1231     assignUniqueIndexToNode();
1232
1233     // compute basis for each node
1234     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1235       HNode node = (HNode) iterator.next();
1236
1237       if (notGenerateSet.contains(node)) {
1238         System.out.println("%%%SKIP =" + node);
1239         continue;
1240       }
1241       Set<Integer> basis = new HashSet<Integer>();
1242       basis.addAll(BASISTOPELEMENT);
1243
1244       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1245       // System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
1246       // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1247       // if a node is reachable from the current node
1248       // need to remove the index of the reachable node from the basis
1249
1250       basis.remove(getHNodeIndex(node));
1251       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1252         HNode reachableNode = (HNode) iterator2.next();
1253         // System.out.println("reachableNode=" + reachableNode);
1254         // System.out.println("getHNodeIndex(reachableNode))="
1255         // + mapHNodeToUniqueIndex.get(reachableNode));
1256         int idx = getHNodeIndex(reachableNode);
1257         basis.remove(idx);
1258       }
1259
1260       mapHNodeToBasis.put(node, basis);
1261     }
1262
1263     // construct the basis set
1264
1265     BasisSet basisSet = new BasisSet();
1266
1267     Set<HNode> keySet = mapHNodeToBasis.keySet();
1268     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1269       HNode node = (HNode) iterator.next();
1270       Set<Integer> basis = mapHNodeToBasis.get(node);
1271       basisSet.addElement(basis, node);
1272     }
1273
1274     return basisSet;
1275
1276   }
1277
1278   public int getHNodeIndex(HNode node) {
1279     return mapHNodeToUniqueIndex.get(node).intValue();
1280   }
1281
1282   public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1283     return mapHNodeToUniqueIndex;
1284   }
1285
1286   public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1287     return mapHNodeToBasis;
1288   }
1289
1290   public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1291
1292     Set<HNode> combinationNodeSet = new HashSet<HNode>();
1293     Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1294     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1295       HNode key = (HNode) iterator.next();
1296
1297       if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1298         combinationNodeSet.add(key);
1299       }
1300     }
1301
1302     return combinationNodeSet;
1303   }
1304
1305   public void writeGraph() {
1306     writeGraph(false);
1307   }
1308
1309   public void writeGraph(boolean isSimple) {
1310
1311     String graphName = "hierarchy" + name;
1312     graphName = graphName.replaceAll("[\\W]", "");
1313
1314     if (isSimple) {
1315       graphName += "_PAPER";
1316     }
1317
1318     // System.out.println("***graphName=" + graphName + "   node siz=" + nodeSet.size());
1319
1320     try {
1321       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1322
1323       bw.write("digraph " + graphName + " {\n");
1324
1325       Iterator<HNode> iter = nodeSet.iterator();
1326
1327       Set<HNode> addedNodeSet = new HashSet<HNode>();
1328
1329       while (iter.hasNext()) {
1330         HNode u = iter.next();
1331
1332         Set<HNode> outSet = getOutgoingNodeSet(u);
1333
1334         if (outSet.size() == 0) {
1335           if (!addedNodeSet.contains(u)) {
1336             if (!isSimple) {
1337               drawNode(bw, u);
1338             } else {
1339               drawNodeName(bw, u);
1340             }
1341             addedNodeSet.add(u);
1342           }
1343         } else {
1344           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1345             HNode v = (HNode) iterator.next();
1346             if (!addedNodeSet.contains(u)) {
1347               if (!isSimple) {
1348                 drawNode(bw, u);
1349               } else {
1350                 drawNodeName(bw, u);
1351               }
1352               addedNodeSet.add(u);
1353             }
1354             if (!addedNodeSet.contains(v)) {
1355               if (!isSimple) {
1356                 drawNode(bw, v);
1357               } else {
1358                 drawNodeName(bw, v);
1359               }
1360               addedNodeSet.add(v);
1361             }
1362             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1363           }
1364         }
1365
1366       }
1367
1368       bw.write("}\n");
1369       bw.close();
1370
1371     } catch (IOException e) {
1372       e.printStackTrace();
1373     }
1374   }
1375
1376   public boolean contains(HNode node) {
1377     return nodeSet.contains(node);
1378   }
1379
1380   public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1381     return getOutgoingNodeSet(src).contains(dst);
1382   }
1383
1384   private String convertMergeSetToString(Set<HNode> mergeSet) {
1385     String str = "";
1386     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1387       HNode merged = (HNode) iterator.next();
1388       if (merged.isMergeNode()) {
1389         str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1390       } else {
1391         str += " " + merged.getName();
1392       }
1393     }
1394     return str;
1395   }
1396
1397   private void drawNodeName(BufferedWriter bw, HNode node) throws IOException {
1398     String nodeName = node.getNamePropertyString();
1399     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1400   }
1401
1402   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1403     String nodeName;
1404     if (node.isMergeNode()) {
1405       nodeName = node.getNamePropertyString();
1406       Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1407       // System.out.println("node=" + node + "   mergeSet=" + mergeSet);
1408       nodeName += ":" + convertMergeSetToString(mergeSet);
1409     } else {
1410       nodeName = node.getNamePropertyString();
1411     }
1412     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1413   }
1414
1415   public int countHopFromTopLocation(HNode node) {
1416
1417     Set<HNode> inNodeSet = getIncomingNodeSet(node);
1418     int count = 0;
1419     if (inNodeSet.size() > 0) {
1420       count = recurCountHopFromTopLocation(inNodeSet, 1);
1421     }
1422
1423     return count;
1424   }
1425
1426   private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1427
1428     int max = curCount;
1429     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1430       HNode node = (HNode) iterator.next();
1431       Set<HNode> inNodeSet = getIncomingNodeSet(node);
1432       if (inNodeSet.size() > 0) {
1433         int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1434         if (max < recurCount) {
1435           max = recurCount;
1436         }
1437       }
1438     }
1439     return max;
1440   }
1441
1442   public Stack<String> computeDistance2(HNode startNode, Set<HNode> endNodeSet,
1443       HierarchyGraph scGraph, Set<HNode> combineSet) {
1444     System.out
1445         .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
1446     Stack<String> trace = new Stack<String>();
1447     return recur_computeDistance2(startNode, endNodeSet, scGraph, 0, combineSet, trace);
1448   }
1449
1450   public Stack<String> computeDistance(HNode startNode, Set<HNode> endNodeSet,
1451       HierarchyGraph scGraph, Set<HNode> combineSet) {
1452     System.out
1453         .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
1454     Stack<String> trace = new Stack<String>();
1455     return recur_computeDistance(startNode, endNodeSet, 0, combineSet, trace);
1456   }
1457
1458   private Stack<String> recur_computeDistance(HNode curNode, Set<HNode> endNodeSet, int count,
1459       Set<HNode> combineSet, Stack<String> trace) {
1460
1461     if (!curNode.isSkeleton()) {
1462       if (curNode.isSharedNode()) {
1463         trace.add("S");
1464       } else {
1465         trace.add("N");
1466       }
1467     }
1468
1469     if (endNodeSet.contains(curNode)) {
1470       // it reaches to one of endNodeSet
1471       return trace;
1472     }
1473
1474     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1475
1476     int curMaxDistance = 0;
1477     Stack<String> curMaxTrace = (Stack<String>) trace.clone();
1478     ;
1479     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1480       HNode inNode = (HNode) iterator.next();
1481       // traverse more...
1482
1483       if (inNode.isCombinationNode() && combineSet != null) {
1484         // check if inNode have the same combination set of the starting node
1485         Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
1486         if (!inNodeCombineSet.equals(combineSet)) {
1487           continue;
1488         }
1489       }
1490
1491       // System.out.println("    traverse more to" + inNode + "  before-trace=" + trace);
1492       Stack<String> newTrace = (Stack<String>) trace.clone();
1493       Stack<String> curTrace =
1494           recur_computeDistance(inNode, endNodeSet, count, combineSet, newTrace);
1495       // System.out.println("curTracerTrace=" + curTrace);
1496
1497       if (curTrace != null && curTrace.size() > curMaxDistance) {
1498         curMaxTrace = curTrace;
1499         curMaxDistance = curTrace.size();
1500       }
1501     }
1502     return curMaxTrace;
1503
1504   }
1505
1506   private Stack<String> recur_computeDistance2(HNode curNode, Set<HNode> endNodeSet,
1507       HierarchyGraph scGraph, int count, Set<HNode> combineSet, Stack<String> trace) {
1508
1509     if (!curNode.isSkeleton()) {
1510       if (curNode.isSharedNode()) {
1511         trace.add("S");
1512       } else {
1513         trace.add("N");
1514       }
1515     }
1516
1517     System.out.println("   curNode=" + curNode + "  curTrace=" + trace);
1518     // System.out.println("     curNode=" + curNode + "  curSCNode="
1519     // + scGraph.getCurrentHNode(curNode) + " contains="
1520     // + endNodeSet.contains(scGraph.getCurrentHNode(curNode)));
1521     if (endNodeSet.contains(scGraph.getCurrentHNode(curNode))) {
1522       // it reaches to one of endNodeSet
1523       return trace;
1524     }
1525
1526     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1527
1528     int curMaxDistance = 0;
1529     Stack<String> curMaxTrace = (Stack<String>) trace.clone();
1530     ;
1531     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1532       HNode inNode = (HNode) iterator.next();
1533       // traverse more...
1534
1535       if (inNode.isCombinationNode() && combineSet != null) {
1536         // check if inNode have the same combination set of the starting node
1537         Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
1538         if (!inNodeCombineSet.equals(combineSet)) {
1539           continue;
1540         }
1541       }
1542
1543       // Stack<String> newTrace = (Stack<String>) trace.clone();
1544       // Stack<String> curTrace =
1545       // recur_computeDistance(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
1546       // if (curTrace != null) {
1547       // return curTrace;
1548       // }
1549
1550       Set<HNode> inReachToNodeSet = getSkeleteNodeSetReachToNoTransitive(inNode);
1551       Set<HNode> inCurReachToNodeSet = new HashSet<HNode>();
1552       for (Iterator iterator2 = inReachToNodeSet.iterator(); iterator2.hasNext();) {
1553         HNode aboveNode = (HNode) iterator2.next();
1554         inCurReachToNodeSet.add(getCurrentHNode(aboveNode));
1555       }
1556
1557       if (combineSet != null || inCurReachToNodeSet.equals(endNodeSet)) {
1558         System.out
1559             .println("        traverse to incomingNode=" + inNode + "  before-trace=" + trace);
1560
1561         Stack<String> newTrace = (Stack<String>) trace.clone();
1562         Stack<String> curTrace =
1563             recur_computeDistance2(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
1564
1565         if (curTrace != null && curTrace.size() > curMaxDistance) {
1566           curMaxTrace = curTrace;
1567           curMaxDistance = curTrace.size();
1568         }
1569       } else {
1570         System.out.println("NOT TRAVERSE a new inNode=" + inNode + " inReachToNodeSet="
1571             + inCurReachToNodeSet);
1572       }
1573
1574     }
1575     return curMaxTrace;
1576   }
1577
1578   public int countNonSharedNode(HNode startNode, Set<HNode> endNodeSet) {
1579     System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
1580     return recur_countNonSharedNode(startNode, endNodeSet, 0);
1581   }
1582
1583   private int recur_countNonSharedNode(HNode startNode, Set<HNode> endNodeSet, int count) {
1584
1585     Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
1586
1587     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1588       HNode inNode = (HNode) iterator.next();
1589       if (endNodeSet.contains(inNode)) {
1590         count++;
1591         return count;
1592       } else {
1593         if (!inNode.isSharedNode()) {
1594           count++;
1595         }
1596         return recur_countNonSharedNode2(inNode, endNodeSet, count);
1597       }
1598     }
1599
1600     return 0;
1601   }
1602
1603   public int countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet) {
1604     System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
1605     return recur_countNonSharedNode2(startNode, endNodeSet, 0);
1606   }
1607
1608   private int recur_countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet, int count) {
1609
1610     Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
1611
1612     if (inNodeSet.size() == 0) {
1613       // it is directly connected to the TOP node
1614     }
1615
1616     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1617       HNode inNode = (HNode) iterator.next();
1618       if (endNodeSet.contains(inNode)) {
1619         return count;
1620       } else {
1621         if (!inNode.isSharedNode()) {
1622           count++;
1623         }
1624         return recur_countNonSharedNode2(inNode, endNodeSet, count);
1625       }
1626     }
1627
1628     // System.out.println("startNode=" + startNode + " inNodeSet=" + inNodeSet);
1629     // HNode inNode = inNodeSet.iterator().next();
1630     return -1;
1631   }
1632
1633   public void removeIsolatedNodes() {
1634     Set<HNode> toberemoved = new HashSet<HNode>();
1635     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1636       HNode node = (HNode) iterator.next();
1637       if (getIncomingNodeSet(node).isEmpty() && getOutgoingNodeSet(node).isEmpty()) {
1638         toberemoved.add(node);
1639       }
1640     }
1641     nodeSet.removeAll(toberemoved);
1642   }
1643 }