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