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
  15 public class HierarchyGraph {
  16
  17   Descriptor desc;
  18
  19   String name;
  20   Map<Descriptor, HNode> mapDescToHNode;
  21   Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
  22   Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
  23   Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
  24   Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
  25   Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
  26   Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
  27   Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
  28
  29   Set<HNode> nodeSet;
  30
  31   public static int seed = 0;
  32
  33   public HierarchyGraph() {
  34     mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
  35     mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
  36     mapHNodeToDescSet = new HashMap<HNode, Set<Descriptor>>();
  37     mapDescToHNode = new HashMap<Descriptor, HNode>();
  38     mapSkeletonNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
  39     mapCombinationNodeToCombineNodeSet = new HashMap<HNode, Set<HNode>>();
  40     mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
  41     mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
  42     nodeSet = new HashSet<HNode>();
  43   }
  44
  45   public Descriptor getDesc() {
  46     return desc;
  47   }
  48
  49   public void setDesc(Descriptor desc) {
  50     this.desc = desc;
  51   }
  52
  53   public String getName() {
  54     return name;
  55   }
  56
  57   public void setName(String name) {
  58     this.name = name;
  59   }
  60
  61   public HierarchyGraph(Descriptor d) {
  62     this();
  63     desc = d;
  64     name = d.toString();
  65   }
  66
  67   public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
  68     return mapHNodeToDescSet;
  69   }
  70
  71   public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
  72     mapHNodeToDescSet.putAll(map);
  73   }
  74
  75   public Map<Descriptor, HNode> getMapDescToHNode() {
  76     return mapDescToHNode;
  77   }
  78
  79   public void setMapDescToHNode(Map<Descriptor, HNode> map) {
  80     mapDescToHNode.putAll(map);
  81   }
  82
  83   public Set<HNode> getNodeSet() {
  84     return nodeSet;
  85   }
  86
  87   public void addEdge(HNode srcHNode, HNode dstHNode) {
  88
  89     if (!nodeSet.contains(srcHNode)) {
  90       nodeSet.add(srcHNode);
  91     }
  92
  93     if (!nodeSet.contains(dstHNode)) {
  94       nodeSet.add(dstHNode);
  95     }
  96
  97     Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
  98
  99     System.out.println("src=" + srcHNode + " dstHNode=" + dstHNode + " possibleCycleSet="
 100         + possibleCycleSet);
 101
 102     if (possibleCycleSet.size() > 0) {
 103       HNode newMergeNode = mergeNodes(possibleCycleSet, false);
 104       newMergeNode.setSharedNode(true);
 105       System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
 106       System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode);
 107     } else {
 108       getIncomingNodeSet(dstHNode).add(srcHNode);
 109       getOutgoingNodeSet(srcHNode).add(dstHNode);
 110       System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
 111     }
 112
 113   }
 114
 115   public void addNode(HNode node) {
 116     nodeSet.add(node);
 117   }
 118
 119   public void addEdge(Descriptor src, Descriptor dst) {
 120     HNode srcHNode = getHNode(src);
 121     HNode dstHNode = getHNode(dst);
 122
 123     addEdge(srcHNode, dstHNode);
 124
 125   }
 126
 127   public void setParamHNode(Descriptor d) {
 128     getHNode(d).setSkeleton(true);
 129   }
 130
 131   public HNode getHNode(Descriptor d) {
 132     if (!mapDescToHNode.containsKey(d)) {
 133       HNode newNode = new HNode(d);
 134       if (d instanceof FieldDescriptor) {
 135         newNode.setSkeleton(true);
 136       }
 137       mappingDescriptorToHNode(d, newNode);
 138       nodeSet.add(newNode);
 139     }
 140     return mapDescToHNode.get(d);
 141   }
 142
 143   private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
 144     mapDescToHNode.put(desc, node);
 145     if (!mapHNodeToDescSet.containsKey(node)) {
 146       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 147     }
 148     mapHNodeToDescSet.get(node).add(desc);
 149   }
 150
 151   public HierarchyGraph generateSkeletonGraph() {
 152
 153     // compose a skeleton graph that only consists of fields or parameters
 154     HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
 155     skeletonGraph.setName(desc + "_SKELETON");
 156
 157     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 158       HNode src = (HNode) iterator.next();
 159       if (src.isSkeleton()) {
 160         Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
 161         if (reachSet.size() > 0) {
 162           for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
 163             HNode dst = (HNode) iterator2.next();
 164             skeletonGraph.addEdge(src, dst);
 165           }
 166         } else {
 167           skeletonGraph.addNode(src);
 168         }
 169       }
 170     }
 171
 172     skeletonGraph.setMapDescToHNode(getMapDescToHNode());
 173     skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
 174
 175     return skeletonGraph;
 176
 177   }
 178
 179   private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
 180
 181     Set<HNode> visited = new HashSet<HNode>();
 182     Set<HNode> connected = new HashSet<HNode>();
 183     recurReachSkeletonSet(node, connected, visited);
 184
 185     return connected;
 186   }
 187
 188   private void removeRedundantEdges() {
 189
 190     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 191       HNode src = (HNode) iterator.next();
 192       Set<HNode> connectedSet = getOutgoingNodeSet(src);
 193       Set<HNode> toberemovedSet = new HashSet<HNode>();
 194       for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 195         HNode dst = (HNode) iterator2.next();
 196         Set<HNode> otherNeighborSet = new HashSet<HNode>();
 197         otherNeighborSet.addAll(connectedSet);
 198         otherNeighborSet.remove(dst);
 199         for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
 200           HNode neighbor = (HNode) iterator3.next();
 201           if (reachTo(neighbor, dst, new HashSet<HNode>())) {
 202             toberemovedSet.add(dst);
 203           }
 204         }
 205       }
 206       if (toberemovedSet.size() > 0) {
 207         connectedSet.removeAll(toberemovedSet);
 208
 209         for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
 210           HNode node = (HNode) iterator2.next();
 211           getIncomingNodeSet(node).remove(src);
 212         }
 213
 214       }
 215     }
 216
 217   }
 218
 219   public void simplifyHierarchyGraph() {
 220     removeRedundantEdges();
 221     combineRedundantNodes(false);
 222   }
 223
 224   public void simplifySkeletonCombinationHierarchyGraph() {
 225     removeRedundantEdges();
 226     combineRedundantNodes(true);
 227   }
 228
 229   private void combineRedundantNodes(boolean onlyCombinationNodes) {
 230     // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
 231     boolean isUpdated = false;
 232     do {
 233       isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes);
 234     } while (isUpdated);
 235   }
 236
 237   private Set<HNode> getIncomingNodeSet(HNode node) {
 238     if (!mapHNodeToIncomingSet.containsKey(node)) {
 239       mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
 240     }
 241     return mapHNodeToIncomingSet.get(node);
 242   }
 243
 244   private Set<HNode> getOutgoingNodeSet(HNode node) {
 245     if (!mapHNodeToOutgoingSet.containsKey(node)) {
 246       mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
 247     }
 248     return mapHNodeToOutgoingSet.get(node);
 249   }
 250
 251   private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes) {
 252     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 253       HNode node1 = (HNode) iterator.next();
 254
 255       if ((onlyCombinationNodes && (!node1.isCombinationNode()))
 256           || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
 257         continue;
 258       }
 259
 260       Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
 261       Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
 262
 263       for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
 264         HNode node2 = (HNode) iterator2.next();
 265
 266         if ((onlyCombinationNodes && (!node2.isCombinationNode()))
 267             || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
 268           continue;
 269         }
 270
 271         if (!node1.equals(node2)) {
 272
 273           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
 274           Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
 275
 276           if (incomingNodeSet1.equals(incomingNodeSet2)
 277               && outgoingNodeSet1.equals(outgoingNodeSet2)) {
 278             // need to merge node1 and node2
 279
 280             Set<HNode> mergeSet = new HashSet<HNode>();
 281             mergeSet.add(node1);
 282             mergeSet.add(node2);
 283             mergeNodes(mergeSet, onlyCombinationNodes);
 284             return true;
 285           }
 286
 287         }
 288       }
 289
 290     }
 291     return false;
 292   }
 293
 294   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
 295     getIncomingNodeSet(dstHNode).add(srcHNode);
 296     getOutgoingNodeSet(srcHNode).add(dstHNode);
 297     System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
 298   }
 299
 300   private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
 301
 302     Set<HNode> incomingNodeSet = new HashSet<HNode>();
 303     Set<HNode> outgoingNodeSet = new HashSet<HNode>();
 304
 305     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 306       HNode node = (HNode) iterator.next();
 307       incomingNodeSet.addAll(getIncomingNodeSet(node));
 308       outgoingNodeSet.addAll(getOutgoingNodeSet(node));
 309     }
 310
 311     String nodeName;
 312     if (onlyCombinationNodes) {
 313       nodeName = "Comb" + (seed++);
 314     } else {
 315       nodeName = "Node" + (seed++);
 316     }
 317     HNode newMergeNode = new HNode(nodeName);
 318
 319     nodeSet.add(newMergeNode);
 320     nodeSet.removeAll(set);
 321
 322     // if the input set contains a skeleton node, need to set a new merge node as skeleton also
 323     boolean hasSkeleton = false;
 324     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 325       HNode inNode = (HNode) iterator.next();
 326       if (inNode.isSkeleton()) {
 327         hasSkeleton = true;
 328         break;
 329       }
 330     }
 331     newMergeNode.setSkeleton(hasSkeleton);
 332
 333     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 334       HNode node = (HNode) iterator.next();
 335       Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
 336       for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
 337         Descriptor desc = (Descriptor) iterator2.next();
 338         mappingDescriptorToHNode(desc, newMergeNode);
 339       }
 340     }
 341
 342     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 343       HNode inNode = (HNode) iterator.next();
 344       Set<HNode> outSet = getOutgoingNodeSet(inNode);
 345       outSet.removeAll(set);
 346       if (!set.contains(inNode)) {
 347         addEdgeWithNoCycleCheck(inNode, newMergeNode);
 348       }
 349     }
 350
 351     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 352       HNode outNode = (HNode) iterator.next();
 353       Set<HNode> inSet = getIncomingNodeSet(outNode);
 354       inSet.removeAll(set);
 355       if (!set.contains(outNode)) {
 356         addEdgeWithNoCycleCheck(newMergeNode, outNode);
 357       }
 358     }
 359
 360     System.out.println("#MERGING NODE=" + set + " new node=" + newMergeNode);
 361     return newMergeNode;
 362   }
 363
 364   private Set<Descriptor> getDescSetOfNode(HNode node) {
 365     if (!mapHNodeToDescSet.containsKey(node)) {
 366       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 367     }
 368     return mapHNodeToDescSet.get(node);
 369   }
 370
 371   private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
 372     Set<HNode> connectedSet = getOutgoingNodeSet(src);
 373     for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
 374       HNode n = iterator.next();
 375       if (n.equals(dst)) {
 376         return true;
 377       }
 378       if (!visited.contains(n)) {
 379         visited.add(n);
 380         if (reachTo(n, dst, visited)) {
 381           return true;
 382         }
 383       }
 384     }
 385     return false;
 386   }
 387
 388   private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
 389
 390     Set<HNode> outSet = getOutgoingNodeSet(node);
 391     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 392       HNode outNode = (HNode) iterator.next();
 393
 394       if (outNode.isSkeleton()) {
 395         connected.add(outNode);
 396       } else if (!visited.contains(outNode)) {
 397         visited.add(outNode);
 398         recurReachSkeletonSet(outNode, connected, visited);
 399       }
 400     }
 401
 402   }
 403
 404   public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
 405     // if an edge from src to dst introduces a new cycle flow,
 406     // the method returns the set of elements consisting of the cycle
 407     Set<HNode> cycleNodeSet = new HashSet<HNode>();
 408     // if the dst node reaches to the src node, the new relation
 409     // introduces a cycle to the lattice
 410     if (dst.equals(src)) {
 411       cycleNodeSet.add(dst);
 412       cycleNodeSet.add(src);
 413     } else if (reachTo(dst, src)) {
 414       cycleNodeSet.add(dst);
 415       cycleNodeSet.add(src);
 416       getInBetweenElements(dst, src, cycleNodeSet);
 417     }
 418     return cycleNodeSet;
 419   }
 420
 421   private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
 422     Set<HNode> connectedSet = getOutgoingNodeSet(start);
 423     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
 424       HNode cur = (HNode) iterator.next();
 425       if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
 426         nodeSet.add(cur);
 427         getInBetweenElements(cur, end, nodeSet);
 428       }
 429     }
 430   }
 431
 432   public boolean reachTo(HNode node1, HNode node2) {
 433     return reachTo(node1, node2, new HashSet<HNode>());
 434   }
 435
 436   public Set<HNode> getCombineSetByCombinationNode(HNode node) {
 437     if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
 438       mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
 439     }
 440     return mapCombinationNodeToCombineNodeSet.get(node);
 441   }
 442
 443   private HNode getCombinationNode(Set<HNode> combineSet) {
 444     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
 445       String name = "COMB" + (seed++);
 446       HNode node = new HNode(name);
 447       node.setCombinationNode(true);
 448       nodeSet.add(node);
 449       mapCombineNodeSetToCombinationNode.put(combineSet, node);
 450       mapCombinationNodeToCombineNodeSet.put(node, combineSet);
 451     }
 452
 453     return mapCombineNodeSetToCombinationNode.get(combineSet);
 454   }
 455
 456   public Set<Set<HNode>> getCombineNodeSet() {
 457     return mapCombineNodeSetToOutgoingNodeSet.keySet();
 458   }
 459
 460   public void insertCombinationNodesToGraph(HierarchyGraph hierarchyGraph) {
 461     // add a new combination node where parameter/field flows are actually combined.
 462
 463     hierarchyGraph.identifyCombinationNodes();
 464
 465     Set<Set<HNode>> keySet = hierarchyGraph.getCombineNodeSet();
 466     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 467       Set<HNode> combineSet = (Set<HNode>) iterator.next();
 468       System.out.println("combineSet=" + combineSet);
 469       HNode combinationNode = getCombinationNode(combineSet);
 470
 471       // add an edge from a skeleton node to a combination node
 472       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
 473         HNode inSkeletonNode = (HNode) iterator2.next();
 474         HNode srcNode = getHNode(inSkeletonNode.getDescriptor());
 475         System.out.println("inSkeletonNode=" + inSkeletonNode + "   srcNode=" + srcNode);
 476         addEdgeWithNoCycleCheck(srcNode, combinationNode);
 477       }
 478
 479       // add an edge from the combination node to outgoing nodes
 480       Set<HNode> outSet = hierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
 481       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 482         HNode curNode = (HNode) iterator2.next();
 483         if (curNode.isCombinationNode()) {
 484           Set<HNode> combineNode = hierarchyGraph.getCombineSetByCombinationNode(curNode);
 485           HNode outNode = getCombinationNode(combineNode);
 486           addEdgeWithNoCycleCheck(combinationNode, outNode);
 487         } else if (curNode.isSkeleton()) {
 488           addEdgeWithNoCycleCheck(combinationNode, curNode);
 489         }
 490       }
 491
 492     }
 493
 494   }
 495
 496   private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
 497     if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
 498       // need to create a new combination node
 499       String nodeName = "Comb" + (seed++);
 500       HNode newCombinationNode = new HNode(nodeName);
 501       newCombinationNode.setCombinationNode(true);
 502
 503       nodeSet.add(newCombinationNode);
 504       mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
 505
 506       for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 507         HNode reachToNode = (HNode) iterator.next();
 508         addEdge(reachToNode, newCombinationNode);
 509       }
 510
 511     }
 512
 513     HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
 514     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
 515       HNode reachableNode = (HNode) iterator.next();
 516       addEdge(combinationNode, reachableNode);
 517     }
 518
 519   }
 520
 521   private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 522
 523     Set<HNode> reachToSet = new HashSet<HNode>();
 524     Set<HNode> visited = new HashSet<HNode>();
 525
 526     recurSkeletonReachTo(node, reachToSet, visited);
 527
 528     return reachToSet;
 529   }
 530
 531   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 532
 533     Set<HNode> inSet = getIncomingNodeSet(node);
 534     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 535       HNode inNode = (HNode) iterator.next();
 536
 537       if (inNode.isSkeleton()) {
 538         reachToSet.add(inNode);
 539       } else if (!visited.contains(inNode)) {
 540         visited.add(inNode);
 541         recurSkeletonReachTo(inNode, reachToSet, visited);
 542       }
 543     }
 544
 545   }
 546
 547   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 548     return mapHNodeToOutgoingSet;
 549   }
 550
 551   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 552     return mapHNodeToIncomingSet;
 553   }
 554
 555   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 556     mapHNodeToOutgoingSet.clear();
 557     Set<HNode> keySet = in.keySet();
 558     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 559       HNode key = (HNode) iterator.next();
 560       Set<HNode> inSet = in.get(key);
 561       Set<HNode> newSet = new HashSet<HNode>();
 562       newSet.addAll(inSet);
 563       mapHNodeToOutgoingSet.put(key, newSet);
 564     }
 565   }
 566
 567   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 568     mapHNodeToIncomingSet.clear();
 569     Set<HNode> keySet = in.keySet();
 570     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 571       HNode key = (HNode) iterator.next();
 572       Set<HNode> inSet = in.get(key);
 573       Set<HNode> newSet = new HashSet<HNode>();
 574       newSet.addAll(inSet);
 575       mapHNodeToIncomingSet.put(key, newSet);
 576     }
 577   }
 578
 579   public void setNodeSet(Set<HNode> inSet) {
 580     nodeSet.clear();
 581     nodeSet.addAll(inSet);
 582   }
 583
 584   public HierarchyGraph clone() {
 585     HierarchyGraph clone = new HierarchyGraph();
 586     clone.setDesc(getDesc());
 587     clone.setName(getName());
 588     clone.setNodeSet(getNodeSet());
 589     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 590     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 591     clone.setMapDescToHNode(getMapDescToHNode());
 592     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 593
 594     return clone;
 595   }
 596
 597   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
 598
 599     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 600       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 601     }
 602     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
 603   }
 604
 605   public void identifyCombinationNodes() {
 606
 607     // 1) set combination node flag if a node combines more than one skeleton node.
 608     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 609       HNode node = (HNode) iterator.next();
 610       if (!node.isSkeleton()) {
 611         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
 612         if (reachToSet.size() > 1) {
 613           node.setCombinationNode(true);
 614           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
 615         }
 616       }
 617     }
 618
 619     // 2) compute the outgoing set that needs to be directly connected from the combination node
 620     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 621       HNode node = (HNode) iterator.next();
 622       if (node.isCombinationNode()) {
 623         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 624         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
 625         addMapCombineSetToOutgoingSet(combineSet, outSet);
 626       }
 627     }
 628
 629   }
 630
 631   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
 632     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 633       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 634     }
 635     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
 636   }
 637
 638   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
 639     // the method returns the set of nodes that are reachable from the current node
 640     // and do not combine the same set of skeleton nodes...
 641
 642     Set<HNode> visited = new HashSet<HNode>();
 643     Set<HNode> reachableSet = new HashSet<HNode>();
 644     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 645
 646     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
 647
 648     return reachableSet;
 649   }
 650
 651   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
 652       Set<HNode> reachableSet, Set<HNode> visited) {
 653
 654     Set<HNode> outSet = getOutgoingNodeSet(node);
 655     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 656       HNode outNode = (HNode) iterator.next();
 657
 658       if (outNode.isCombinationNode()) {
 659         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
 660         if (combineSetOfOutNode.equals(combineSet)) {
 661           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
 662               visited);
 663         } else {
 664           reachableSet.add(outNode);
 665         }
 666       } else if (outNode.isSkeleton()) {
 667         reachableSet.add(outNode);
 668       }
 669
 670     }
 671
 672   }
 673
 674   public void writeGraph() {
 675
 676     String graphName = "hierarchy" + name;
 677     graphName = graphName.replaceAll("[\\W]", "");
 678
 679     try {
 680       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 681
 682       bw.write("digraph " + graphName + " {\n");
 683
 684       Iterator<HNode> iter = nodeSet.iterator();
 685
 686       Set<HNode> addedNodeSet = new HashSet<HNode>();
 687
 688       while (iter.hasNext()) {
 689         HNode u = iter.next();
 690
 691         Set<HNode> outSet = getOutgoingNodeSet(u);
 692
 693         if (outSet.size() == 0) {
 694           if (!addedNodeSet.contains(u)) {
 695             drawNode(bw, u);
 696             addedNodeSet.add(u);
 697           }
 698         } else {
 699           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 700             HNode v = (HNode) iterator.next();
 701             if (!addedNodeSet.contains(u)) {
 702               drawNode(bw, u);
 703               addedNodeSet.add(u);
 704             }
 705             if (!addedNodeSet.contains(v)) {
 706               drawNode(bw, v);
 707               addedNodeSet.add(v);
 708             }
 709             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
 710           }
 711         }
 712
 713       }
 714
 715       bw.write("}\n");
 716       bw.close();
 717
 718     } catch (IOException e) {
 719       e.printStackTrace();
 720     }
 721   }
 722
 723   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
 724     String shared = "";
 725     if (node.isSharedNode()) {
 726       shared = "*";
 727     }
 728     bw.write(node.getName() + " [label=\"" + node.getName() + shared + "\"]" + ";\n");
 729   }
 730
 731 }