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