Robust/src/Analysis/SSJava/HierarchyGraph.java

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