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(LocationInference infer) {
 302     removeRedundantEdges();
 303     combineRedundantNodes(false, infer);
 304   }
 305
 306   public void combineRedundantNodes(boolean onlyCombinationNodes, LocationInference infer) {
 307     // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
 308     boolean isUpdated = false;
 309     do {
 310       isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes, infer);
 311     } while (isUpdated);
 312   }
 313
 314   public Set<HNode> getIncomingNodeSet(HNode node) {
 315     if (!mapHNodeToIncomingSet.containsKey(node)) {
 316       mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
 317     }
 318     return mapHNodeToIncomingSet.get(node);
 319   }
 320
 321   public Set<HNode> getOutgoingNodeSet(HNode node) {
 322     if (!mapHNodeToOutgoingSet.containsKey(node)) {
 323       mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
 324     }
 325     return mapHNodeToOutgoingSet.get(node);
 326   }
 327
 328   private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes, LocationInference infer) {
 329     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 330       HNode node1 = (HNode) iterator.next();
 331
 332       if ((onlyCombinationNodes && (!node1.isCombinationNode()))
 333           || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
 334         continue;
 335       }
 336
 337       Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
 338       Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
 339
 340       for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
 341         HNode node2 = (HNode) iterator2.next();
 342
 343         if ((onlyCombinationNodes && (!node2.isCombinationNode()))
 344             || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
 345           continue;
 346         }
 347
 348         if (!isEligibleForMerging(node1, node2)) {
 349           continue;
 350         }
 351
 352         if (!node1.equals(node2)) {
 353
 354           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
 355           Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
 356
 357           if (incomingNodeSet1.equals(incomingNodeSet2)
 358               && outgoingNodeSet1.equals(outgoingNodeSet2)) {
 359             // need to merge node1 and node2
 360
 361             // ///////////////
 362             // merge two nodes only if every hierarchy graph in the inheritance hierarchy
 363             // that includes both nodes allows the merging of them...
 364             Set<HNode> mergeSet = new HashSet<HNode>();
 365             mergeSet.add(node1);
 366             mergeSet.add(node2);
 367             infer.isValidMergeInheritanceCheck(desc, mergeSet);
 368
 369             // ///////////////
 370
 371             mergeNodes(mergeSet, onlyCombinationNodes);
 372             return true;
 373           }
 374
 375         }
 376       }
 377
 378     }
 379     return false;
 380   }
 381
 382   private boolean isEligibleForMerging(HNode node1, HNode node2) {
 383
 384     if (node1.isSharedNode() || node2.isSharedNode()) {
 385
 386       // if either of nodes is a shared node,
 387       // all descriptors of node1 & node2 should have a primitive type
 388
 389       Set<Descriptor> descSet = new HashSet<Descriptor>();
 390       descSet.addAll(getDescSetOfNode(node1));
 391       descSet.addAll(getDescSetOfNode(node2));
 392
 393       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 394         Descriptor desc = (Descriptor) iterator.next();
 395         if (!LocationInference.isPrimitive(desc)) {
 396           return false;
 397         }
 398       }
 399       return true;
 400     }
 401     return false;
 402   }
 403
 404   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
 405     getIncomingNodeSet(dstHNode).add(srcHNode);
 406     getOutgoingNodeSet(srcHNode).add(dstHNode);
 407     // System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
 408   }
 409
 410   private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
 411
 412     Set<HNode> incomingNodeSet = new HashSet<HNode>();
 413     Set<HNode> outgoingNodeSet = new HashSet<HNode>();
 414
 415     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 416       HNode node = (HNode) iterator.next();
 417       incomingNodeSet.addAll(getIncomingNodeSet(node));
 418       outgoingNodeSet.addAll(getOutgoingNodeSet(node));
 419     }
 420
 421     String nodeName;
 422     boolean isMergeNode = false;
 423     if (onlyCombinationNodes) {
 424       nodeName = "Comb" + (LocationInference.locSeed++);
 425     } else {
 426       nodeName = "Node" + (LocationInference.locSeed++);
 427       isMergeNode = true;
 428     }
 429     HNode newMergeNode = new HNode(nodeName);
 430     newMergeNode.setMergeNode(isMergeNode);
 431
 432     nodeSet.add(newMergeNode);
 433     nodeSet.removeAll(set);
 434
 435     // if the input set contains a skeleton node, need to set a new merge node as skeleton also
 436     boolean hasSkeleton = false;
 437     boolean hasShared = false;
 438     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 439       HNode inNode = (HNode) iterator.next();
 440       if (inNode.isSkeleton()) {
 441         hasSkeleton = true;
 442       }
 443       if (inNode.isSharedNode()) {
 444         hasShared = true;
 445       }
 446     }
 447     // System.out.println("-----Set merging node=" + newMergeNode + " as a skeleton=" + set
 448     // + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
 449     newMergeNode.setSkeleton(hasSkeleton);
 450     newMergeNode.setSharedNode(hasShared);
 451
 452     System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
 453
 454     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 455       HNode node = (HNode) iterator.next();
 456       Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
 457       for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
 458         Descriptor desc = (Descriptor) iterator2.next();
 459         mappingDescriptorToHNode(desc, newMergeNode);
 460       }
 461     }
 462
 463     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 464       HNode inNode = (HNode) iterator.next();
 465       Set<HNode> outSet = getOutgoingNodeSet(inNode);
 466       outSet.removeAll(set);
 467       if (!set.contains(inNode)) {
 468         addEdgeWithNoCycleCheck(inNode, newMergeNode);
 469       }
 470     }
 471
 472     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 473       HNode outNode = (HNode) iterator.next();
 474       Set<HNode> inSet = getIncomingNodeSet(outNode);
 475       inSet.removeAll(set);
 476       if (!set.contains(outNode)) {
 477         addEdgeWithNoCycleCheck(newMergeNode, outNode);
 478       }
 479     }
 480
 481     Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
 482     for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
 483       HNode merged = iter.next();
 484       if (merged.isSkeleton()) {
 485         mergedSkeletonNode.add(merged);
 486       }
 487     }
 488
 489     // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
 490     // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 491     mapMergeNodetoMergingSet.put(newMergeNode, set);
 492     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 493       HNode mergedNode = (HNode) iterator.next();
 494       addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
 495     }
 496
 497     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 498       HNode hNode = (HNode) iterator.next();
 499       System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
 500     }
 501
 502     System.out.println();
 503
 504     return newMergeNode;
 505   }
 506
 507   private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
 508
 509     if (curNode.isMergeNode()) {
 510       Set<HNode> mergingSet = getMergingSet(curNode);
 511       mergingSet.add(curNode);
 512       System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
 513           + mergingSet + " newNode=" + newNode);
 514       for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
 515         HNode mergingNode = (HNode) iterator.next();
 516         mapHNodeToCurrentHNode.put(mergingNode, newNode);
 517         mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
 518       }
 519     } else {
 520       mapHNodeToCurrentHNode.put(curNode, newNode);
 521       mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
 522     }
 523
 524   }
 525
 526   public HNode getCurrentHNode(HNode node) {
 527     if (!mapHNodeToCurrentHNode.containsKey(node)) {
 528       mapHNodeToCurrentHNode.put(node, node);
 529     }
 530     return mapHNodeToCurrentHNode.get(node);
 531   }
 532
 533   public HNode getCurrentHNode(String nodeName) {
 534     return mapHNodeNameToCurrentHNode.get(nodeName);
 535   }
 536
 537   private Set<HNode> getMergingSet(HNode mergeNode) {
 538     Set<HNode> mergingSet = new HashSet<HNode>();
 539     Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
 540     for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
 541       HNode node = (HNode) iterator.next();
 542       if (node.isMergeNode()) {
 543         mergingSet.add(node);
 544         mergingSet.addAll(getMergingSet(node));
 545       } else {
 546         mergingSet.add(node);
 547       }
 548     }
 549     return mergingSet;
 550   }
 551
 552   public Set<Descriptor> getDescSetOfNode(HNode node) {
 553     if (!mapHNodeToDescSet.containsKey(node)) {
 554       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 555     }
 556     return mapHNodeToDescSet.get(node);
 557   }
 558
 559   private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
 560     Set<HNode> connectedSet = getOutgoingNodeSet(src);
 561     for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
 562       HNode n = iterator.next();
 563       if (n.equals(dst)) {
 564         return true;
 565       }
 566       if (!visited.contains(n)) {
 567         visited.add(n);
 568         if (reachTo(n, dst, visited)) {
 569           return true;
 570         }
 571       }
 572     }
 573     return false;
 574   }
 575
 576   private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
 577
 578     Set<HNode> outSet = getOutgoingNodeSet(node);
 579     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 580       HNode outNode = (HNode) iterator.next();
 581
 582       if (outNode.isSkeleton()) {
 583         connected.add(outNode);
 584       } else if (!visited.contains(outNode)) {
 585         visited.add(outNode);
 586         recurReachSkeletonSet(outNode, connected, visited);
 587       }
 588     }
 589
 590   }
 591
 592   public Set<HNode> getReachableSCNodeSet(HNode startNode) {
 593     // returns the set of hnodes which is reachable from the startNode and is either SC node or a
 594     // node which is directly connected to the SC nodes
 595     Set<HNode> reachable = new HashSet<HNode>();
 596     Set<HNode> visited = new HashSet<HNode>();
 597     visited.add(startNode);
 598     recurReachableNodeSet(startNode, visited, reachable);
 599     return reachable;
 600   }
 601
 602   public Set<HNode> getSCNodeReachToSet(HNode node) {
 603     if (!mapNormalNodeToSCNodeReachToSet.containsKey(node)) {
 604       mapNormalNodeToSCNodeReachToSet.put(node, new HashSet<HNode>());
 605     }
 606     return mapNormalNodeToSCNodeReachToSet.get(node);
 607   }
 608
 609   private void recurReachableNodeSet(HNode node, Set<HNode> visited, Set<HNode> reachable) {
 610
 611     Set<HNode> outSet = getOutgoingNodeSet(node);
 612     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 613       HNode out = (HNode) iterator.next();
 614
 615       if (!visited.contains(out)) {
 616         visited.add(out);
 617         Set<HNode> reachableFromSCNodeSet = reachableFromSCNode(out);
 618         mapNormalNodeToSCNodeReachToSet.put(out, reachableFromSCNodeSet);
 619         if (out.isSkeleton() || out.isCombinationNode() || reachableFromSCNodeSet.size() > 0) {
 620           reachable.add(out);
 621         } else {
 622           visited.add(out);
 623           recurReachableNodeSet(out, visited, reachable);
 624         }
 625
 626       }
 627
 628     }
 629
 630   }
 631
 632   private Set<HNode> reachableFromSCNode(HNode node) {
 633     Set<HNode> visited = new HashSet<HNode>();
 634     visited.add(node);
 635     Set<HNode> reachable = new HashSet<HNode>();
 636     recurReachableFromSCNode(node, reachable, visited);
 637     return reachable;
 638   }
 639
 640   private void recurReachableFromSCNode(HNode node, Set<HNode> reachable, Set<HNode> visited) {
 641     Set<HNode> inNodeSet = getIncomingNodeSet(node);
 642     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 643       HNode inNode = (HNode) iterator.next();
 644       if (inNode.isSkeleton() || inNode.isCombinationNode()) {
 645         visited.add(inNode);
 646         reachable.add(inNode);
 647       } else if (!visited.contains(inNode)) {
 648         visited.add(inNode);
 649         recurReachableFromSCNode(inNode, reachable, visited);
 650       }
 651     }
 652   }
 653
 654   public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
 655       Set<HNode> combinationNodeSet) {
 656     Set<HNode> reachable = new HashSet<HNode>();
 657     Set<HNode> visited = new HashSet<HNode>();
 658     visited.add(node);
 659     recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
 660     return reachable;
 661   }
 662
 663   public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
 664       Set<HNode> reachable, Set<HNode> combinationNodeSet) {
 665
 666     Set<HNode> outSet = getOutgoingNodeSet(node);
 667     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 668       HNode out = (HNode) iterator.next();
 669
 670       if (!visited.contains(out)) {
 671         visited.add(out);
 672         if (out.isSkeleton()) {
 673           reachable.add(out);
 674         } else if (out.isCombinationNode()) {
 675           if (combinationNodeSet == null) {
 676             reachable.add(out);
 677           } else if (!combinationNodeSet.contains(out)) {
 678             reachable.add(out);
 679           } else {
 680             recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 681                 combinationNodeSet);
 682           }
 683         } else {
 684           recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 685               combinationNodeSet);
 686         }
 687
 688       }
 689
 690     }
 691
 692   }
 693
 694   public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
 695     Set<HNode> visited = new HashSet<HNode>();
 696     return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
 697   }
 698
 699   public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
 700
 701     Set<HNode> outSet = getOutgoingNodeSet(node);
 702     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 703       HNode out = (HNode) iterator.next();
 704       // if (!visited.contains(out)) {
 705       if (out.isCombinationNode() || out.isSkeleton()) {
 706         return out;
 707       } else {
 708         // visited.add(out);
 709         return getDirectlyReachableSkeletonCombinationNodeFrom(out);
 710       }
 711     }
 712     // }
 713
 714     return null;
 715   }
 716
 717   public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
 718     // if an edge from src to dst introduces a new cycle flow,
 719     // the method returns the set of elements consisting of the cycle
 720     Set<HNode> cycleNodeSet = new HashSet<HNode>();
 721     // if the dst node reaches to the src node, the new relation
 722     // introduces a cycle to the lattice
 723     if (dst.equals(src)) {
 724       cycleNodeSet.add(dst);
 725       cycleNodeSet.add(src);
 726     } else if (reachTo(dst, src)) {
 727       cycleNodeSet.add(dst);
 728       cycleNodeSet.add(src);
 729       getInBetweenElements(dst, src, cycleNodeSet);
 730     }
 731     return cycleNodeSet;
 732   }
 733
 734   private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
 735     Set<HNode> connectedSet = getOutgoingNodeSet(start);
 736     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
 737       HNode cur = (HNode) iterator.next();
 738       if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
 739         nodeSet.add(cur);
 740         getInBetweenElements(cur, end, nodeSet);
 741       }
 742     }
 743   }
 744
 745   public boolean reachTo(HNode node1, HNode node2) {
 746     return reachTo(node1, node2, new HashSet<HNode>());
 747   }
 748
 749   public Set<HNode> getCombineSetByCombinationNode(HNode node) {
 750     if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
 751       mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
 752     }
 753     return mapCombinationNodeToCombineNodeSet.get(node);
 754   }
 755
 756   public HNode getCombinationNode(Set<HNode> combineSet) {
 757     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
 758       String name = "COMB" + (LocationInference.locSeed++);
 759       HNode node = new HNode(name);
 760       node.setCombinationNode(true);
 761       nodeSet.add(node);
 762       mapCombineNodeSetToCombinationNode.put(combineSet, node);
 763       mapCombinationNodeToCombineNodeSet.put(node, combineSet);
 764     }
 765
 766     return mapCombineNodeSetToCombinationNode.get(combineSet);
 767   }
 768
 769   public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
 770     return mapCombineNodeSetToCombinationNode;
 771   }
 772
 773   public Set<Set<HNode>> getCombineNodeSet() {
 774     return mapCombineNodeSetToOutgoingNodeSet.keySet();
 775   }
 776
 777   public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
 778     // add a new combination node where parameter/field flows are actually combined.
 779
 780     simpleHierarchyGraph.identifyCombinationNodes();
 781
 782     Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
 783     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 784       Set<HNode> combineSet = (Set<HNode>) iterator.next();
 785       // System.out.println("--combineSet=" + combineSet);
 786       HNode combinationNode = getCombinationNode(combineSet);
 787       System.out.println("--combinationNode=" + combinationNode + "   combineSet=" + combineSet);
 788
 789       System.out.println("--hierarchynodes="
 790           + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
 791       // add an edge from a skeleton node to a combination node
 792       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
 793         HNode inSkeletonNode = (HNode) iterator2.next();
 794         // System.out.println("--inSkeletonNode=" + inSkeletonNode + "  desc="
 795         // + inSkeletonNode.getDescriptor());
 796         HNode srcNode;
 797         if (inSkeletonNode.getDescriptor() == null) {
 798           // the node is merging one...
 799           srcNode = inSkeletonNode;
 800         } else {
 801           srcNode = getHNode(inSkeletonNode.getDescriptor());
 802         }
 803         // System.out.println("--srcNode=" + srcNode);
 804         addEdgeWithNoCycleCheck(srcNode, combinationNode);
 805       }
 806
 807       // add an edge from the combination node to outgoing nodes
 808       Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
 809       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 810         HNode curNode = (HNode) iterator2.next();
 811         if (curNode.isCombinationNode()) {
 812           Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
 813           HNode outNode = getCombinationNode(combineNode);
 814           addEdgeWithNoCycleCheck(combinationNode, outNode);
 815         } else if (curNode.isSkeleton()) {
 816           // HNode dstNode2 = getHNode(curNode.getDescriptor());
 817           HNode dstNode = getCurrentHNode(curNode);
 818           // System.out.println("-----curNode=" + curNode + "------->" + dstNode + "    dstNode2="
 819           // + dstNode2);
 820           addEdgeWithNoCycleCheck(combinationNode, dstNode);
 821         }
 822       }
 823
 824       System.out.println("--");
 825
 826     }
 827
 828   }
 829
 830   private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
 831     if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
 832       // need to create a new combination node
 833       String nodeName = "Comb" + (LocationInference.locSeed++);
 834       HNode newCombinationNode = new HNode(nodeName);
 835       newCombinationNode.setCombinationNode(true);
 836
 837       nodeSet.add(newCombinationNode);
 838       mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
 839
 840       for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 841         HNode reachToNode = (HNode) iterator.next();
 842         addEdge(reachToNode, newCombinationNode);
 843       }
 844
 845     }
 846
 847     HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
 848     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
 849       HNode reachableNode = (HNode) iterator.next();
 850       addEdge(combinationNode, reachableNode);
 851     }
 852
 853   }
 854
 855   private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 856
 857     Set<HNode> reachToSet = new HashSet<HNode>();
 858     Set<HNode> visited = new HashSet<HNode>();
 859     // visited.add(node);
 860     recurSkeletonReachTo(node, reachToSet, visited);
 861
 862     // obsolete!
 863     // if a node reaches to one of elements in the reachToSet, we do not need to keep it
 864     // because the node is not directly connected to the combination node
 865     // removeRedundantReachToNodes(reachToSet);
 866
 867     return reachToSet;
 868   }
 869
 870   private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
 871
 872     Set<HNode> toberemoved = new HashSet<HNode>();
 873     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 874       HNode cur = (HNode) iterator.next();
 875
 876       for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
 877         HNode dst = (HNode) iterator2.next();
 878         if (!cur.equals(dst) && reachTo(cur, dst)) {
 879           // it is redundant
 880           toberemoved.add(cur);
 881         }
 882       }
 883     }
 884     reachToSet.removeAll(toberemoved);
 885   }
 886
 887   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 888
 889     Set<HNode> inSet = getIncomingNodeSet(node);
 890     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 891       HNode inNode = (HNode) iterator.next();
 892
 893       if (inNode.isSkeleton()) {
 894         visited.add(inNode);
 895         reachToSet.add(inNode);
 896       } else if (!visited.contains(inNode)) {
 897         visited.add(inNode);
 898         recurSkeletonReachTo(inNode, reachToSet, visited);
 899       }
 900     }
 901
 902   }
 903
 904   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 905     return mapHNodeToOutgoingSet;
 906   }
 907
 908   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 909     return mapHNodeToIncomingSet;
 910   }
 911
 912   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 913     mapHNodeToOutgoingSet.clear();
 914     Set<HNode> keySet = in.keySet();
 915     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 916       HNode key = (HNode) iterator.next();
 917       Set<HNode> inSet = in.get(key);
 918       Set<HNode> newSet = new HashSet<HNode>();
 919       newSet.addAll(inSet);
 920       mapHNodeToOutgoingSet.put(key, newSet);
 921     }
 922   }
 923
 924   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 925     mapHNodeToIncomingSet.clear();
 926     Set<HNode> keySet = in.keySet();
 927     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 928       HNode key = (HNode) iterator.next();
 929       Set<HNode> inSet = in.get(key);
 930       Set<HNode> newSet = new HashSet<HNode>();
 931       newSet.addAll(inSet);
 932       mapHNodeToIncomingSet.put(key, newSet);
 933     }
 934   }
 935
 936   public void setNodeSet(Set<HNode> inSet) {
 937     nodeSet.clear();
 938     nodeSet.addAll(inSet);
 939   }
 940
 941   public HierarchyGraph clone() {
 942     HierarchyGraph clone = new HierarchyGraph();
 943     clone.setDesc(getDesc());
 944     clone.setName(getName());
 945     clone.setNodeSet(getNodeSet());
 946     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 947     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 948     clone.setMapDescToHNode(getMapDescToHNode());
 949     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 950     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 951     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 952     clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
 953
 954     return clone;
 955   }
 956
 957   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
 958     return mapMergeNodetoMergingSet;
 959   }
 960
 961   public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
 962     this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
 963   }
 964
 965   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
 966
 967     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 968       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 969     }
 970     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
 971   }
 972
 973   public void identifyCombinationNodes() {
 974
 975     // 1) set combination node flag if a node combines more than one skeleton node.
 976     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 977       HNode node = (HNode) iterator.next();
 978       if (!node.isSkeleton()) {
 979         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
 980         // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
 981         // reachToSet = removeTransitivelyReachToSet(reachToSet);
 982         Set<HNode> tempSet = reachToSet;
 983         System.out.println("$node=" + node + "   reachToNodeSet=" + reachToSet + " tempSet="
 984             + tempSet);
 985         if (reachToSet.size() > 1) {
 986           // if (countSkeletonNodes(reachToSet) > 1) {
 987           System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
 988           System.out.println("-set combinationnode=" + node);
 989           node.setCombinationNode(true);
 990           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
 991         }
 992       }
 993     }
 994
 995     // 2) compute the outgoing set that needs to be directly connected from the combination node
 996     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 997       HNode node = (HNode) iterator.next();
 998       if (node.isCombinationNode()) {
 999         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1000         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
1001         addMapCombineSetToOutgoingSet(combineSet, outSet);
1002       }
1003     }
1004
1005   }
1006
1007   private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
1008
1009     Set<HNode> toberemoved = new HashSet<HNode>();
1010     Set<HNode> visited = new HashSet<HNode>();
1011     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
1012       HNode node = (HNode) iterator.next();
1013       visited.add(node);
1014       recurIsReachingTo(node, reachToSet, toberemoved, visited);
1015     }
1016
1017     Set<HNode> rSet = new HashSet<HNode>();
1018     rSet.addAll(reachToSet);
1019     rSet.removeAll(toberemoved);
1020     return rSet;
1021   }
1022
1023   private void recurIsReachingTo(HNode curNode, Set<HNode> reachToSet, Set<HNode> toberemoved,
1024       Set<HNode> visited) {
1025     Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1026
1027     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1028       HNode inNode = (HNode) iterator.next();
1029       if (reachToSet.contains(inNode)) {
1030         toberemoved.add(inNode);
1031       } else if (!visited.contains(inNode)) {
1032         visited.add(inNode);
1033         recurIsReachingTo(inNode, reachToSet, toberemoved, visited);
1034       }
1035     }
1036
1037   }
1038
1039   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
1040     return mapCombinationNodeToCombineNodeSet;
1041   }
1042
1043   public int countSkeletonNodes(Set<HNode> set) {
1044     int count = 0;
1045
1046     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1047       HNode node = (HNode) iterator.next();
1048       Set<Descriptor> descSet = getDescSetOfNode(node);
1049       count += descSet.size();
1050     }
1051
1052     return count;
1053   }
1054
1055   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
1056     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1057       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1058     }
1059     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
1060   }
1061
1062   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
1063     // the method returns the set of nodes that are reachable from the current node
1064     // and do not combine the same set of skeleton nodes...
1065
1066     Set<HNode> visited = new HashSet<HNode>();
1067     Set<HNode> reachableSet = new HashSet<HNode>();
1068     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1069
1070     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
1071
1072     return reachableSet;
1073   }
1074
1075   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
1076       Set<HNode> reachableSet, Set<HNode> visited) {
1077
1078     Set<HNode> outSet = getOutgoingNodeSet(node);
1079     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1080       HNode outNode = (HNode) iterator.next();
1081
1082       if (outNode.isCombinationNode()) {
1083         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
1084         if (combineSetOfOutNode.equals(combineSet)) {
1085           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
1086               visited);
1087         } else {
1088           reachableSet.add(outNode);
1089         }
1090       } else if (outNode.isSkeleton()) {
1091         reachableSet.add(outNode);
1092       }
1093
1094     }
1095
1096   }
1097
1098   private Set<HNode> getReachableNodeSetFrom(HNode node) {
1099
1100     Set<HNode> reachableSet = new HashSet<HNode>();
1101     Set<HNode> visited = new HashSet<HNode>();
1102
1103     recurReachableNodeSetFrom(node, reachableSet, visited);
1104
1105     return reachableSet;
1106   }
1107
1108   private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
1109
1110     Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
1111     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
1112       HNode outNode = (HNode) iterator.next();
1113       reachableSet.add(outNode);
1114       if (!visited.contains(outNode)) {
1115         visited.add(outNode);
1116         recurReachableNodeSetFrom(outNode, reachableSet, visited);
1117       }
1118     }
1119
1120   }
1121
1122   public void assignUniqueIndexToNode() {
1123     int idx = 1;
1124     // System.out.println("nodeSet=" + nodeSet);
1125     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1126       HNode node = (HNode) iterator.next();
1127       mapHNodeToUniqueIndex.put(node, idx);
1128       idx++;
1129     }
1130
1131     BASISTOPELEMENT = new HashSet<Integer>();
1132     for (int i = 1; i < idx + 1; i++) {
1133       BASISTOPELEMENT.add(i);
1134     }
1135   }
1136
1137   public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1138
1139     // assign a unique index to a node
1140     assignUniqueIndexToNode();
1141
1142     // compute basis for each node
1143     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1144       HNode node = (HNode) iterator.next();
1145
1146       if (notGenerateSet.contains(node)) {
1147         System.out.println("%%%SKIP =" + node);
1148         continue;
1149       }
1150       Set<Integer> basis = new HashSet<Integer>();
1151       basis.addAll(BASISTOPELEMENT);
1152
1153       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1154       // System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
1155       // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1156       // if a node is reachable from the current node
1157       // need to remove the index of the reachable node from the basis
1158
1159       basis.remove(getHNodeIndex(node));
1160       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1161         HNode reachableNode = (HNode) iterator2.next();
1162         // System.out.println("reachableNode=" + reachableNode);
1163         // System.out.println("getHNodeIndex(reachableNode))="
1164         // + mapHNodeToUniqueIndex.get(reachableNode));
1165         int idx = getHNodeIndex(reachableNode);
1166         basis.remove(idx);
1167       }
1168
1169       mapHNodeToBasis.put(node, basis);
1170     }
1171
1172     // construct the basis set
1173
1174     BasisSet basisSet = new BasisSet();
1175
1176     Set<HNode> keySet = mapHNodeToBasis.keySet();
1177     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1178       HNode node = (HNode) iterator.next();
1179       Set<Integer> basis = mapHNodeToBasis.get(node);
1180       basisSet.addElement(basis, node);
1181     }
1182
1183     return basisSet;
1184
1185   }
1186
1187   public int getHNodeIndex(HNode node) {
1188     return mapHNodeToUniqueIndex.get(node).intValue();
1189   }
1190
1191   public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1192     return mapHNodeToUniqueIndex;
1193   }
1194
1195   public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1196     return mapHNodeToBasis;
1197   }
1198
1199   public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1200
1201     Set<HNode> combinationNodeSet = new HashSet<HNode>();
1202     Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1203     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1204       HNode key = (HNode) iterator.next();
1205
1206       if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1207         combinationNodeSet.add(key);
1208       }
1209     }
1210
1211     return combinationNodeSet;
1212   }
1213
1214   public void writeGraph() {
1215     writeGraph(false);
1216   }
1217
1218   public void writeGraph(boolean isSimple) {
1219
1220     String graphName = "hierarchy" + name;
1221     System.out.println("#GRAPHNAME=" + graphName);
1222     graphName = graphName.replaceAll("[\\W]", "");
1223
1224     if (isSimple) {
1225       graphName += "_PAPER";
1226     }
1227
1228     // System.out.println("***graphName=" + graphName + "   node siz=" + nodeSet.size());
1229
1230     try {
1231       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1232
1233       bw.write("digraph " + graphName + " {\n");
1234
1235       Iterator<HNode> iter = nodeSet.iterator();
1236
1237       Set<HNode> addedNodeSet = new HashSet<HNode>();
1238
1239       while (iter.hasNext()) {
1240         HNode u = iter.next();
1241
1242         Set<HNode> outSet = getOutgoingNodeSet(u);
1243
1244         if (outSet.size() == 0) {
1245           if (!addedNodeSet.contains(u)) {
1246             if (!isSimple) {
1247               drawNode(bw, u);
1248             } else {
1249               drawNodeName(bw, u);
1250             }
1251             addedNodeSet.add(u);
1252           }
1253         } else {
1254           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1255             HNode v = (HNode) iterator.next();
1256             if (!addedNodeSet.contains(u)) {
1257               if (!isSimple) {
1258                 drawNode(bw, u);
1259               } else {
1260                 drawNodeName(bw, u);
1261               }
1262               addedNodeSet.add(u);
1263             }
1264             if (!addedNodeSet.contains(v)) {
1265               if (!isSimple) {
1266                 drawNode(bw, v);
1267               } else {
1268                 drawNodeName(bw, v);
1269               }
1270               addedNodeSet.add(v);
1271             }
1272             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1273           }
1274         }
1275
1276       }
1277
1278       bw.write("}\n");
1279       bw.close();
1280
1281     } catch (IOException e) {
1282       e.printStackTrace();
1283     }
1284   }
1285
1286   public boolean contains(HNode node) {
1287     return nodeSet.contains(node);
1288   }
1289
1290   public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1291     return getOutgoingNodeSet(src).contains(dst);
1292   }
1293
1294   private String convertMergeSetToString(Set<HNode> mergeSet) {
1295     String str = "";
1296     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1297       HNode merged = (HNode) iterator.next();
1298       if (merged.isMergeNode()) {
1299         str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1300       } else {
1301         str += " " + merged.getName();
1302       }
1303     }
1304     return str;
1305   }
1306
1307   private void drawNodeName(BufferedWriter bw, HNode node) throws IOException {
1308     String nodeName = node.getNamePropertyString();
1309     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1310   }
1311
1312   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1313     String nodeName;
1314     if (node.isMergeNode()) {
1315       nodeName = node.getNamePropertyString();
1316       Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1317       System.out.println("node=" + node + "   mergeSet=" + mergeSet);
1318       nodeName += ":" + convertMergeSetToString(mergeSet);
1319     } else {
1320       nodeName = node.getNamePropertyString();
1321     }
1322     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1323   }
1324
1325   public int countHopFromTopLocation(HNode node) {
1326
1327     Set<HNode> inNodeSet = getIncomingNodeSet(node);
1328     int count = 0;
1329     if (inNodeSet.size() > 0) {
1330       count = recurCountHopFromTopLocation(inNodeSet, 1);
1331     }
1332
1333     return count;
1334   }
1335
1336   private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1337
1338     int max = curCount;
1339     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1340       HNode node = (HNode) iterator.next();
1341       Set<HNode> inNodeSet = getIncomingNodeSet(node);
1342       if (inNodeSet.size() > 0) {
1343         int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1344         if (max < recurCount) {
1345           max = recurCount;
1346         }
1347       }
1348     }
1349     return max;
1350   }
1351
1352 }