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       // add an edge from a skeleton node to a combination node
 787       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
 788         HNode inSkeletonNode = (HNode) iterator2.next();
 789         // System.out.println("--inSkeletonNode=" + inSkeletonNode + "  desc="
 790         // + inSkeletonNode.getDescriptor());
 791         HNode srcNode;
 792         if (inSkeletonNode.getDescriptor() == null) {
 793           // the node is merging one...
 794           srcNode = inSkeletonNode;
 795         } else {
 796           srcNode = getHNode(inSkeletonNode.getDescriptor());
 797         }
 798         // System.out.println("--srcNode=" + srcNode);
 799         addEdgeWithNoCycleCheck(srcNode, combinationNode);
 800       }
 801
 802       // add an edge from the combination node to outgoing nodes
 803       Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
 804       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 805         HNode curNode = (HNode) iterator2.next();
 806         if (curNode.isCombinationNode()) {
 807           Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
 808           HNode outNode = getCombinationNode(combineNode);
 809           addEdgeWithNoCycleCheck(combinationNode, outNode);
 810         } else if (curNode.isSkeleton()) {
 811           // HNode dstNode2 = getHNode(curNode.getDescriptor());
 812           HNode dstNode = getCurrentHNode(curNode);
 813           // System.out.println("-----curNode=" + curNode + "------->" + dstNode + "    dstNode2="
 814           // + dstNode2);
 815           addEdgeWithNoCycleCheck(combinationNode, dstNode);
 816         }
 817       }
 818
 819       System.out.println("--");
 820
 821     }
 822
 823   }
 824
 825   private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
 826     if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
 827       // need to create a new combination node
 828       String nodeName = "Comb" + (LocationInference.locSeed++);
 829       HNode newCombinationNode = new HNode(nodeName);
 830       newCombinationNode.setCombinationNode(true);
 831
 832       nodeSet.add(newCombinationNode);
 833       mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
 834
 835       for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 836         HNode reachToNode = (HNode) iterator.next();
 837         addEdge(reachToNode, newCombinationNode);
 838       }
 839
 840     }
 841
 842     HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
 843     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
 844       HNode reachableNode = (HNode) iterator.next();
 845       addEdge(combinationNode, reachableNode);
 846     }
 847
 848   }
 849
 850   private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 851
 852     Set<HNode> reachToSet = new HashSet<HNode>();
 853     Set<HNode> visited = new HashSet<HNode>();
 854     // visited.add(node);
 855     recurSkeletonReachTo(node, reachToSet, visited);
 856
 857     // obsolete!
 858     // if a node reaches to one of elements in the reachToSet, we do not need to keep it
 859     // because the node is not directly connected to the combination node
 860     // removeRedundantReachToNodes(reachToSet);
 861
 862     return reachToSet;
 863   }
 864
 865   private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
 866
 867     Set<HNode> toberemoved = new HashSet<HNode>();
 868     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 869       HNode cur = (HNode) iterator.next();
 870
 871       for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
 872         HNode dst = (HNode) iterator2.next();
 873         if (!cur.equals(dst) && reachTo(cur, dst)) {
 874           // it is redundant
 875           toberemoved.add(cur);
 876         }
 877       }
 878     }
 879     reachToSet.removeAll(toberemoved);
 880   }
 881
 882   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 883
 884     Set<HNode> inSet = getIncomingNodeSet(node);
 885     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 886       HNode inNode = (HNode) iterator.next();
 887
 888       if (inNode.isSkeleton()) {
 889         visited.add(inNode);
 890         reachToSet.add(inNode);
 891       } else if (!visited.contains(inNode)) {
 892         visited.add(inNode);
 893         recurSkeletonReachTo(inNode, reachToSet, visited);
 894       }
 895     }
 896
 897   }
 898
 899   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 900     return mapHNodeToOutgoingSet;
 901   }
 902
 903   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 904     return mapHNodeToIncomingSet;
 905   }
 906
 907   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 908     mapHNodeToOutgoingSet.clear();
 909     Set<HNode> keySet = in.keySet();
 910     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 911       HNode key = (HNode) iterator.next();
 912       Set<HNode> inSet = in.get(key);
 913       Set<HNode> newSet = new HashSet<HNode>();
 914       newSet.addAll(inSet);
 915       mapHNodeToOutgoingSet.put(key, newSet);
 916     }
 917   }
 918
 919   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 920     mapHNodeToIncomingSet.clear();
 921     Set<HNode> keySet = in.keySet();
 922     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 923       HNode key = (HNode) iterator.next();
 924       Set<HNode> inSet = in.get(key);
 925       Set<HNode> newSet = new HashSet<HNode>();
 926       newSet.addAll(inSet);
 927       mapHNodeToIncomingSet.put(key, newSet);
 928     }
 929   }
 930
 931   public void setNodeSet(Set<HNode> inSet) {
 932     nodeSet.clear();
 933     nodeSet.addAll(inSet);
 934   }
 935
 936   public HierarchyGraph clone() {
 937     HierarchyGraph clone = new HierarchyGraph();
 938     clone.setDesc(getDesc());
 939     clone.setName(getName());
 940     clone.setNodeSet(getNodeSet());
 941     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 942     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 943     clone.setMapDescToHNode(getMapDescToHNode());
 944     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 945     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 946     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 947     clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
 948
 949     return clone;
 950   }
 951
 952   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
 953     return mapMergeNodetoMergingSet;
 954   }
 955
 956   public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
 957     this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
 958   }
 959
 960   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
 961
 962     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 963       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 964     }
 965     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
 966   }
 967
 968   public void identifyCombinationNodes() {
 969
 970     // 1) set combination node flag if a node combines more than one skeleton node.
 971     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 972       HNode node = (HNode) iterator.next();
 973       if (!node.isSkeleton()) {
 974         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
 975         System.out.println("$node=" + node + "   reachToNodeSet=" + reachToSet);
 976         if (reachToSet.size() > 1) {
 977           // if (countSkeletonNodes(reachToSet) > 1) {
 978           System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
 979           System.out.println("-set combinationnode=" + node);
 980           node.setCombinationNode(true);
 981           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
 982         }
 983       }
 984     }
 985
 986     // 2) compute the outgoing set that needs to be directly connected from the combination node
 987     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 988       HNode node = (HNode) iterator.next();
 989       if (node.isCombinationNode()) {
 990         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 991         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
 992         addMapCombineSetToOutgoingSet(combineSet, outSet);
 993       }
 994     }
 995
 996   }
 997
 998   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
 999     return mapCombinationNodeToCombineNodeSet;
1000   }
1001
1002   public int countSkeletonNodes(Set<HNode> set) {
1003     int count = 0;
1004
1005     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1006       HNode node = (HNode) iterator.next();
1007       Set<Descriptor> descSet = getDescSetOfNode(node);
1008       count += descSet.size();
1009     }
1010
1011     return count;
1012   }
1013
1014   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
1015     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1016       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1017     }
1018     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
1019   }
1020
1021   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
1022     // the method returns the set of nodes that are reachable from the current node
1023     // and do not combine the same set of skeleton nodes...
1024
1025     Set<HNode> visited = new HashSet<HNode>();
1026     Set<HNode> reachableSet = new HashSet<HNode>();
1027     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1028
1029     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
1030
1031     return reachableSet;
1032   }
1033
1034   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
1035       Set<HNode> reachableSet, Set<HNode> visited) {
1036
1037     Set<HNode> outSet = getOutgoingNodeSet(node);
1038     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1039       HNode outNode = (HNode) iterator.next();
1040
1041       if (outNode.isCombinationNode()) {
1042         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
1043         if (combineSetOfOutNode.equals(combineSet)) {
1044           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
1045               visited);
1046         } else {
1047           reachableSet.add(outNode);
1048         }
1049       } else if (outNode.isSkeleton()) {
1050         reachableSet.add(outNode);
1051       }
1052
1053     }
1054
1055   }
1056
1057   private Set<HNode> getReachableNodeSetFrom(HNode node) {
1058
1059     Set<HNode> reachableSet = new HashSet<HNode>();
1060     Set<HNode> visited = new HashSet<HNode>();
1061
1062     recurReachableNodeSetFrom(node, reachableSet, visited);
1063
1064     return reachableSet;
1065   }
1066
1067   private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
1068
1069     Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
1070     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
1071       HNode outNode = (HNode) iterator.next();
1072       reachableSet.add(outNode);
1073       if (!visited.contains(outNode)) {
1074         visited.add(outNode);
1075         recurReachableNodeSetFrom(outNode, reachableSet, visited);
1076       }
1077     }
1078
1079   }
1080
1081   public void assignUniqueIndexToNode() {
1082     int idx = 1;
1083     // System.out.println("nodeSet=" + nodeSet);
1084     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1085       HNode node = (HNode) iterator.next();
1086       mapHNodeToUniqueIndex.put(node, idx);
1087       idx++;
1088     }
1089
1090     BASISTOPELEMENT = new HashSet<Integer>();
1091     for (int i = 1; i < idx + 1; i++) {
1092       BASISTOPELEMENT.add(i);
1093     }
1094   }
1095
1096   public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1097
1098     // assign a unique index to a node
1099     assignUniqueIndexToNode();
1100
1101     // compute basis for each node
1102     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1103       HNode node = (HNode) iterator.next();
1104
1105       if (notGenerateSet.contains(node)) {
1106         System.out.println("%%%SKIP =" + node);
1107         continue;
1108       }
1109       Set<Integer> basis = new HashSet<Integer>();
1110       basis.addAll(BASISTOPELEMENT);
1111
1112       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1113       // System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
1114       // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1115       // if a node is reachable from the current node
1116       // need to remove the index of the reachable node from the basis
1117
1118       basis.remove(getHNodeIndex(node));
1119       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1120         HNode reachableNode = (HNode) iterator2.next();
1121         // System.out.println("reachableNode=" + reachableNode);
1122         // System.out.println("getHNodeIndex(reachableNode))="
1123         // + mapHNodeToUniqueIndex.get(reachableNode));
1124         int idx = getHNodeIndex(reachableNode);
1125         basis.remove(idx);
1126       }
1127
1128       mapHNodeToBasis.put(node, basis);
1129     }
1130
1131     // construct the basis set
1132
1133     BasisSet basisSet = new BasisSet();
1134
1135     Set<HNode> keySet = mapHNodeToBasis.keySet();
1136     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1137       HNode node = (HNode) iterator.next();
1138       Set<Integer> basis = mapHNodeToBasis.get(node);
1139       basisSet.addElement(basis, node);
1140     }
1141
1142     return basisSet;
1143
1144   }
1145
1146   public int getHNodeIndex(HNode node) {
1147     return mapHNodeToUniqueIndex.get(node).intValue();
1148   }
1149
1150   public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1151     return mapHNodeToUniqueIndex;
1152   }
1153
1154   public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1155     return mapHNodeToBasis;
1156   }
1157
1158   public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1159
1160     Set<HNode> combinationNodeSet = new HashSet<HNode>();
1161     Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1162     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1163       HNode key = (HNode) iterator.next();
1164
1165       if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1166         combinationNodeSet.add(key);
1167       }
1168     }
1169
1170     return combinationNodeSet;
1171   }
1172
1173   public void writeGraph() {
1174     writeGraph(false);
1175   }
1176
1177   public void writeGraph(boolean isSimple) {
1178
1179     String graphName = "hierarchy" + name;
1180     graphName = graphName.replaceAll("[\\W]", "");
1181
1182     if (isSimple) {
1183       graphName += "_PAPER";
1184     }
1185
1186     try {
1187       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1188
1189       bw.write("digraph " + graphName + " {\n");
1190
1191       Iterator<HNode> iter = nodeSet.iterator();
1192
1193       Set<HNode> addedNodeSet = new HashSet<HNode>();
1194
1195       while (iter.hasNext()) {
1196         HNode u = iter.next();
1197
1198         Set<HNode> outSet = getOutgoingNodeSet(u);
1199
1200         if (outSet.size() == 0) {
1201           if (!addedNodeSet.contains(u)) {
1202             if (!isSimple) {
1203               drawNode(bw, u);
1204             } else {
1205               drawNodeName(bw, u);
1206             }
1207             addedNodeSet.add(u);
1208           }
1209         } else {
1210           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1211             HNode v = (HNode) iterator.next();
1212             if (!addedNodeSet.contains(u)) {
1213               if (!isSimple) {
1214                 drawNode(bw, u);
1215               } else {
1216                 drawNodeName(bw, u);
1217               }
1218               addedNodeSet.add(u);
1219             }
1220             if (!addedNodeSet.contains(v)) {
1221               if (!isSimple) {
1222                 drawNode(bw, v);
1223               } else {
1224                 drawNodeName(bw, v);
1225               }
1226               addedNodeSet.add(v);
1227             }
1228             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1229           }
1230         }
1231
1232       }
1233
1234       bw.write("}\n");
1235       bw.close();
1236
1237     } catch (IOException e) {
1238       e.printStackTrace();
1239     }
1240   }
1241
1242   public boolean contains(HNode node) {
1243     return nodeSet.contains(node);
1244   }
1245
1246   public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1247     return getOutgoingNodeSet(src).contains(dst);
1248   }
1249
1250   private String convertMergeSetToString(Set<HNode> mergeSet) {
1251     String str = "";
1252     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1253       HNode merged = (HNode) iterator.next();
1254       if (merged.isMergeNode()) {
1255         str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1256       } else {
1257         str += " " + merged.getName();
1258       }
1259     }
1260     return str;
1261   }
1262
1263   private void drawNodeName(BufferedWriter bw, HNode node) throws IOException {
1264     String nodeName = node.getNamePropertyString();
1265     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1266   }
1267
1268   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1269     String nodeName;
1270     if (node.isMergeNode()) {
1271       nodeName = node.getNamePropertyString();
1272       Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1273       nodeName += ":" + convertMergeSetToString(mergeSet);
1274     } else {
1275       nodeName = node.getNamePropertyString();
1276     }
1277     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1278   }
1279
1280   public int countHopFromTopLocation(HNode node) {
1281
1282     Set<HNode> inNodeSet = getIncomingNodeSet(node);
1283     int count = 0;
1284     if (inNodeSet.size() > 0) {
1285       count = recurCountHopFromTopLocation(inNodeSet, 1);
1286     }
1287
1288     return count;
1289   }
1290
1291   private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1292
1293     int max = curCount;
1294     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1295       HNode node = (HNode) iterator.next();
1296       Set<HNode> inNodeSet = getIncomingNodeSet(node);
1297       if (inNodeSet.size() > 0) {
1298         int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1299         if (max < recurCount) {
1300           max = recurCount;
1301         }
1302       }
1303     }
1304     return max;
1305   }
1306
1307 }