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