1 package Analysis.SSJava;
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;
11 import java.util.Stack;
14 import IR.FieldDescriptor;
16 public class HierarchyGraph {
25 Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
26 Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
28 Map<Descriptor, HNode> mapDescToHNode;
29 Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
30 Map<HNode, HNode> mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node
31 Map<String, HNode> mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial
33 Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
35 // data structures for a combination node
36 Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
37 Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
38 Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
39 Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
41 Map<HNode, Set<HNode>> mapNormalNodeToSCNodeReachToSet;
43 Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToFirstNodeOfChainSet;
47 // for the lattice generation
48 Map<HNode, Integer> mapHNodeToUniqueIndex;
49 Map<HNode, Set<Integer>> mapHNodeToBasis;
50 Set<Integer> BASISTOPELEMENT;
52 public HierarchyGraph() {
53 mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
54 mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
55 mapHNodeToDescSet = new HashMap<HNode, Set<Descriptor>>();
56 mapDescToHNode = new HashMap<Descriptor, HNode>();
57 mapSkeletonNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
58 mapCombinationNodeToCombineNodeSet = new HashMap<HNode, Set<HNode>>();
59 mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
60 mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
61 nodeSet = new HashSet<HNode>();
63 mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
64 mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
66 mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
68 mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
70 mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
72 mapNormalNodeToSCNodeReachToSet = new HashMap<HNode, Set<HNode>>();
74 mapCombineNodeSetToFirstNodeOfChainSet = new HashMap<Set<HNode>, Set<HNode>>();
79 public void setSCGraph(boolean in) {
83 public boolean isSCGraph() {
87 public Descriptor getDesc() {
91 public void setDesc(Descriptor desc) {
95 public String getName() {
99 public void setName(String name) {
103 public HierarchyGraph(Descriptor d) {
109 public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
110 return mapHNodeToDescSet;
113 public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
114 mapHNodeToDescSet.putAll(map);
117 public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
118 return mapHNodeToCurrentHNode;
121 public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
122 return mapHNodeNameToCurrentHNode;
125 public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
126 this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
129 public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
130 this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
133 public Map<Descriptor, HNode> getMapDescToHNode() {
134 return mapDescToHNode;
137 public void setMapDescToHNode(Map<Descriptor, HNode> map) {
138 mapDescToHNode.putAll(map);
141 public Set<HNode> getNodeSet() {
145 public void addEdge(HNode srcHNode, HNode dstHNode) {
147 if (!nodeSet.contains(srcHNode)) {
148 nodeSet.add(srcHNode);
151 if (!nodeSet.contains(dstHNode)) {
152 nodeSet.add(dstHNode);
155 Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
157 if (possibleCycleSet.size() > 0) {
159 if (possibleCycleSet.size() == 1) {
160 // System.out.println("possibleCycleSet=" + possibleCycleSet + " from src=" + srcHNode
161 // + " dstHNode=" + dstHNode);
162 if (dstHNode.isSharedNode()) {
163 // it has already been assigned shared node.
165 dstHNode.setSharedNode(true);
166 // System.out.println("$$$setShared=" + dstHNode);
171 // System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
172 HNode newMergeNode = mergeNodes(possibleCycleSet);
173 newMergeNode.setSharedNode(true);
176 getIncomingNodeSet(dstHNode).add(srcHNode);
177 getOutgoingNodeSet(srcHNode).add(dstHNode);
178 // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
183 public void addNode(HNode node) {
187 public void addEdge(Descriptor src, Descriptor dst) {
189 if (src.equals(LocationInference.LITERALDESC)) {
190 // in this case, we do not need to add a source hnode
191 // just add a destination hnode
194 HNode srcHNode = getHNode(src);
195 HNode dstHNode = getHNode(dst);
196 addEdge(srcHNode, dstHNode);
201 public void setParamHNode(Descriptor d) {
202 getHNode(d).setSkeleton(true);
205 public HNode getHNode(Descriptor d) {
206 if (!mapDescToHNode.containsKey(d)) {
207 HNode newNode = new HNode(d);
209 if (d instanceof FieldDescriptor) {
210 newNode.setSkeleton(true);
213 if (d.equals(LocationInference.TOPDESC)) {
214 newNode.setSkeleton(true);
217 String symbol = d.getSymbol();
218 if (symbol.startsWith(LocationInference.PCLOC) || symbol.startsWith(LocationInference.RLOC)) {
219 newNode.setSkeleton(true);
222 mappingDescriptorToHNode(d, newNode);
223 nodeSet.add(newNode);
225 return mapDescToHNode.get(d);
228 public HNode getHNode(String name) {
229 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
230 HNode node = (HNode) iterator.next();
231 if (node.getName().equals(name)) {
238 private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
239 mapDescToHNode.put(desc, node);
240 if (!mapHNodeToDescSet.containsKey(node)) {
241 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
243 mapHNodeToDescSet.get(node).add(desc);
246 public HierarchyGraph generateSkeletonGraph() {
248 // compose a skeleton graph that only consists of fields or parameters
249 HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
250 skeletonGraph.setName(desc + "_SKELETON");
252 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
253 HNode src = (HNode) iterator.next();
254 if (src.isSkeleton()) {
255 Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
256 if (reachSet.size() > 0) {
257 for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
258 HNode dst = (HNode) iterator2.next();
259 skeletonGraph.addEdge(src, dst);
262 skeletonGraph.addNode(src);
267 skeletonGraph.setMapDescToHNode(getMapDescToHNode());
268 skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
269 skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
270 skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
271 skeletonGraph.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
273 return skeletonGraph;
277 private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
279 Set<HNode> visited = new HashSet<HNode>();
280 Set<HNode> connected = new HashSet<HNode>();
281 recurReachSkeletonSet(node, connected, visited);
286 public void removeRedundantEdges() {
288 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
289 HNode src = (HNode) iterator.next();
290 Set<HNode> connectedSet = getOutgoingNodeSet(src);
291 Set<HNode> toberemovedSet = new HashSet<HNode>();
292 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
293 HNode dst = (HNode) iterator2.next();
294 Set<HNode> otherNeighborSet = new HashSet<HNode>();
295 otherNeighborSet.addAll(connectedSet);
296 otherNeighborSet.remove(dst);
297 for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
298 HNode neighbor = (HNode) iterator3.next();
299 if (reachTo(neighbor, dst, new HashSet<HNode>())) {
300 toberemovedSet.add(dst);
304 if (toberemovedSet.size() > 0) {
305 connectedSet.removeAll(toberemovedSet);
307 for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
308 HNode node = (HNode) iterator2.next();
309 getIncomingNodeSet(node).remove(src);
317 public void simplifyHierarchyGraph(LocationInference infer) {
318 removeRedundantEdges();
319 combineRedundantNodes(infer);
322 public void combineRedundantNodes(LocationInference infer) {
323 // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
324 boolean isUpdated = false;
326 isUpdated = combineTwoRedundatnNodes(infer);
330 public Set<HNode> getIncomingNodeSet(HNode node) {
331 if (!mapHNodeToIncomingSet.containsKey(node)) {
332 mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
334 return mapHNodeToIncomingSet.get(node);
337 public Set<HNode> getOutgoingNodeSet(HNode node) {
338 if (!mapHNodeToOutgoingSet.containsKey(node)) {
339 mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
341 return mapHNodeToOutgoingSet.get(node);
344 private boolean combineTwoRedundatnNodes(LocationInference infer) {
345 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
346 HNode node1 = (HNode) iterator.next();
348 // if ((onlyCombinationNodes && (!node1.isCombinationNode()))
349 // || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
353 if (!node1.isSkeleton()) {
357 Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
358 Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
360 for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
361 HNode node2 = (HNode) iterator2.next();
363 // if ((onlyCombinationNodes && (!node2.isCombinationNode()))
364 // || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
368 if (!node2.isSkeleton()) {
372 // System.out.println("node1=" + node1 + " vs node2=" + node2);
373 if (!isEligibleForMerging(node1, node2)) {
377 if (!node1.equals(node2)) {
379 Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
380 Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
382 // System.out.println(node1 + " " + node2 + " MERGING incoming?=" + incomingNodeSet1
383 // + " vs " + incomingNodeSet2);
384 // System.out.println(node1 + " " + node2 + " MERGING outgoing?=" + outgoingNodeSet1
385 // + " vs " + outgoingNodeSet2);
387 if (incomingNodeSet1.equals(incomingNodeSet2)
388 && outgoingNodeSet1.equals(outgoingNodeSet2)) {
389 // need to merge node1 and node2
390 // System.out.println("MERGE!!!!!!!!!!!!!");
392 // merge two nodes only if every hierarchy graph in the inheritance hierarchy
393 // that includes both nodes allows the merging of them...
394 Set<HNode> mergeSet = new HashSet<HNode>();
397 infer.isValidMergeInheritanceCheck(desc, mergeSet);
401 mergeNodes(mergeSet);
412 private boolean isEligibleForMerging(HNode node1, HNode node2) {
414 if (node1.isSharedNode() || node2.isSharedNode()) {
416 // if either of nodes is a shared node,
417 // all descriptors of node1 & node2 should have a primitive type
419 Set<Descriptor> descSet = new HashSet<Descriptor>();
420 descSet.addAll(getDescSetOfNode(node1));
421 descSet.addAll(getDescSetOfNode(node2));
423 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
424 Descriptor desc = (Descriptor) iterator.next();
425 if (!LocationInference.isPrimitive(desc)) {
434 private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
435 getIncomingNodeSet(dstHNode).add(srcHNode);
436 getOutgoingNodeSet(srcHNode).add(dstHNode);
437 // System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
440 private HNode mergeNodes(Set<HNode> set) {
442 Set<HNode> incomingNodeSet = new HashSet<HNode>();
443 Set<HNode> outgoingNodeSet = new HashSet<HNode>();
445 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
446 HNode node = (HNode) iterator.next();
447 incomingNodeSet.addAll(getIncomingNodeSet(node));
448 outgoingNodeSet.addAll(getOutgoingNodeSet(node));
452 boolean isMergeNode = false;
453 nodeName = "MNode" + (LocationInference.locSeed++);
456 HNode newMergeNode = new HNode(nodeName);
457 newMergeNode.setMergeNode(isMergeNode);
459 nodeSet.add(newMergeNode);
460 nodeSet.removeAll(set);
462 // if the input set contains a skeleton node, need to set a new merge node as skeleton also
463 boolean hasSkeleton = false;
464 boolean hasShared = false;
465 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
466 HNode inNode = (HNode) iterator.next();
467 if (inNode.isSkeleton()) {
470 if (inNode.isSharedNode()) {
474 // System.out.println("-----Set merging node=" + newMergeNode + " as a skeleton=" + set
475 // + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
476 newMergeNode.setSkeleton(hasSkeleton);
477 newMergeNode.setSharedNode(hasShared);
479 // System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
481 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
482 HNode node = (HNode) iterator.next();
483 Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
484 for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
485 Descriptor desc = (Descriptor) iterator2.next();
486 mappingDescriptorToHNode(desc, newMergeNode);
490 for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
491 HNode inNode = (HNode) iterator.next();
492 Set<HNode> outSet = getOutgoingNodeSet(inNode);
493 outSet.removeAll(set);
494 if (!set.contains(inNode)) {
495 addEdgeWithNoCycleCheck(inNode, newMergeNode);
499 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
500 HNode outNode = (HNode) iterator.next();
501 Set<HNode> inSet = getIncomingNodeSet(outNode);
502 inSet.removeAll(set);
503 if (!set.contains(outNode)) {
504 addEdgeWithNoCycleCheck(newMergeNode, outNode);
508 Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
509 for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
510 HNode merged = iter.next();
511 if (merged.isSkeleton()) {
512 mergedSkeletonNode.add(merged);
516 // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
517 // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
518 mapMergeNodetoMergingSet.put(newMergeNode, set);
519 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
520 HNode mergedNode = (HNode) iterator.next();
521 addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
524 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
525 HNode hNode = (HNode) iterator.next();
526 // System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
529 // System.out.println();
534 private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
536 if (curNode.isMergeNode()) {
537 Set<HNode> mergingSet = getMergingSet(curNode);
538 mergingSet.add(curNode);
539 // System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
540 // + mergingSet + " newNode=" + newNode);
541 for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
542 HNode mergingNode = (HNode) iterator.next();
543 mapHNodeToCurrentHNode.put(mergingNode, newNode);
544 mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
547 mapHNodeToCurrentHNode.put(curNode, newNode);
548 mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
553 public HNode getCurrentHNode(HNode node) {
554 if (!mapHNodeToCurrentHNode.containsKey(node)) {
555 mapHNodeToCurrentHNode.put(node, node);
557 return mapHNodeToCurrentHNode.get(node);
560 public HNode getCurrentHNode(String nodeName) {
561 return mapHNodeNameToCurrentHNode.get(nodeName);
564 private Set<HNode> getMergingSet(HNode mergeNode) {
565 Set<HNode> mergingSet = new HashSet<HNode>();
566 Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
567 for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
568 HNode node = (HNode) iterator.next();
569 if (node.isMergeNode()) {
570 mergingSet.add(node);
571 mergingSet.addAll(getMergingSet(node));
573 mergingSet.add(node);
579 public Set<Descriptor> getDescSetOfNode(HNode node) {
580 if (!mapHNodeToDescSet.containsKey(node)) {
581 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
583 return mapHNodeToDescSet.get(node);
586 private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
587 Set<HNode> connectedSet = getOutgoingNodeSet(src);
588 for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
589 HNode n = iterator.next();
593 if (!visited.contains(n)) {
595 if (reachTo(n, dst, visited)) {
603 private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
605 Set<HNode> outSet = getOutgoingNodeSet(node);
606 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
607 HNode outNode = (HNode) iterator.next();
609 if (outNode.isSkeleton()) {
610 connected.add(outNode);
611 } else if (!visited.contains(outNode)) {
612 visited.add(outNode);
613 recurReachSkeletonSet(outNode, connected, visited);
619 public Set<HNode> getReachableSCNodeSet(HNode startNode) {
620 // returns the set of hnodes which is reachable from the startNode and is either SC node or a
621 // node which is directly connected to the SC nodes
622 Set<HNode> reachable = new HashSet<HNode>();
623 Set<HNode> visited = new HashSet<HNode>();
624 visited.add(startNode);
625 recurReachableNodeSet(startNode, visited, reachable);
629 public Set<HNode> getSCNodeReachToSet(HNode node) {
630 if (!mapNormalNodeToSCNodeReachToSet.containsKey(node)) {
631 mapNormalNodeToSCNodeReachToSet.put(node, new HashSet<HNode>());
633 return mapNormalNodeToSCNodeReachToSet.get(node);
636 private void recurReachableNodeSet(HNode node, Set<HNode> visited, Set<HNode> reachable) {
638 Set<HNode> outSet = getOutgoingNodeSet(node);
639 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
640 HNode out = (HNode) iterator.next();
642 if (!visited.contains(out)) {
644 Set<HNode> reachableFromSCNodeSet = reachableFromSCNode(out);
645 mapNormalNodeToSCNodeReachToSet.put(out, reachableFromSCNodeSet);
646 if (out.isSkeleton() || out.isCombinationNode() || reachableFromSCNodeSet.size() > 0) {
650 recurReachableNodeSet(out, visited, reachable);
659 private Set<HNode> reachableFromSCNode(HNode node) {
660 Set<HNode> visited = new HashSet<HNode>();
662 Set<HNode> reachable = new HashSet<HNode>();
663 recurReachableFromSCNode(node, reachable, visited);
667 private void recurReachableFromSCNode(HNode node, Set<HNode> reachable, Set<HNode> visited) {
668 Set<HNode> inNodeSet = getIncomingNodeSet(node);
669 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
670 HNode inNode = (HNode) iterator.next();
671 if (inNode.isSkeleton() || inNode.isCombinationNode()) {
673 reachable.add(inNode);
674 } else if (!visited.contains(inNode)) {
676 recurReachableFromSCNode(inNode, reachable, visited);
681 public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
682 Set<HNode> combinationNodeSet) {
683 Set<HNode> reachable = new HashSet<HNode>();
684 Set<HNode> visited = new HashSet<HNode>();
686 recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
690 public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
691 Set<HNode> reachable, Set<HNode> combinationNodeSet) {
693 Set<HNode> outSet = getOutgoingNodeSet(node);
694 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
695 HNode out = (HNode) iterator.next();
697 if (!visited.contains(out)) {
699 if (out.isSkeleton()) {
701 } else if (out.isCombinationNode()) {
702 if (combinationNodeSet == null) {
704 } else if (!combinationNodeSet.contains(out)) {
707 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
711 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
721 public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
722 Set<HNode> visited = new HashSet<HNode>();
723 return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
726 public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
728 Set<HNode> outSet = getOutgoingNodeSet(node);
729 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
730 HNode out = (HNode) iterator.next();
731 // if (!visited.contains(out)) {
732 if (out.isCombinationNode() || out.isSkeleton()) {
736 return getDirectlyReachableSkeletonCombinationNodeFrom(out);
744 public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
745 // if an edge from src to dst introduces a new cycle flow,
746 // the method returns the set of elements consisting of the cycle
747 Set<HNode> cycleNodeSet = new HashSet<HNode>();
748 // if the dst node reaches to the src node, the new relation
749 // introduces a cycle to the lattice
750 if (dst.equals(src)) {
751 cycleNodeSet.add(dst);
752 cycleNodeSet.add(src);
753 } else if (reachTo(dst, src)) {
754 cycleNodeSet.add(dst);
755 cycleNodeSet.add(src);
756 getInBetweenElements(dst, src, cycleNodeSet);
761 private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
762 Set<HNode> connectedSet = getOutgoingNodeSet(start);
763 for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
764 HNode cur = (HNode) iterator.next();
765 if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
767 getInBetweenElements(cur, end, nodeSet);
772 public boolean reachTo(HNode node1, HNode node2) {
773 return reachTo(node1, node2, new HashSet<HNode>());
776 public Set<HNode> getCombineSetByCombinationNode(HNode node) {
777 if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
778 mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
780 return mapCombinationNodeToCombineNodeSet.get(node);
783 public HNode getCombinationNode(Set<HNode> combineSet) {
785 if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
786 String name = "COMB" + (LocationInference.locSeed++);
787 System.out.println("-NEW COMB NODE=" + name);
788 HNode node = new HNode(name);
789 node.setCombinationNode(true);
791 mapCombineNodeSetToCombinationNode.put(combineSet, node);
792 mapCombinationNodeToCombineNodeSet.put(node, combineSet);
795 return mapCombineNodeSetToCombinationNode.get(combineSet);
798 public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
799 return mapCombineNodeSetToCombinationNode;
802 public Set<Set<HNode>> getCombineNodeSet() {
803 return mapCombineNodeSetToOutgoingNodeSet.keySet();
806 public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
807 // add a new combination node where parameter/field flows are actually combined.
809 simpleHierarchyGraph.identifyCombinationNodes();
811 Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
812 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
813 Set<HNode> combineSet = (Set<HNode>) iterator.next();
814 HNode combinationNode = getCombinationNode(combineSet);
815 System.out.println("\n@INSERT COMBINATION NODE FOR combineSet=" + combineSet
816 + " --combinationNode=" + combinationNode);
817 System.out.println(" --hierarchynodes="
818 + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
820 Set<HNode> simpleHNodeSet =
821 simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet);
823 // check whether a hnode in the simple hierarchy graph is the first node of the chain
824 // if all incoming combination nodes to the hnode have a different combination set from the
825 // hnode, it is the first node of the chain
826 for (Iterator iterator2 = simpleHNodeSet.iterator(); iterator2.hasNext();) {
827 HNode simpleHNode = (HNode) iterator2.next();
828 boolean isFirstNodeOfChain = true;
829 Set<HNode> incomingNodeSet = simpleHierarchyGraph.getIncomingNodeSet(simpleHNode);
830 for (Iterator iterator3 = incomingNodeSet.iterator(); iterator3.hasNext();) {
831 HNode inNode = (HNode) iterator3.next();
832 if (inNode.isCombinationNode()) {
833 Set<HNode> inNodeCombineSet =
834 simpleHierarchyGraph.getCombineSetByCombinationNode(inNode);
835 if (inNodeCombineSet.equals(combineSet)) {
836 isFirstNodeOfChain = false;
841 simpleHNode.setDirectCombinationNode(isFirstNodeOfChain);
842 if (isFirstNodeOfChain) {
843 simpleHierarchyGraph.addFirstNodeOfChain(combineSet, simpleHNode);
844 System.out.println("IT IS THE FIRST NODE OF THE CHAIN:" + simpleHNode);
845 // System.out.println("--->INCOMING NODES=");
846 // Set<HNode> inNodeSet = simpleHierarchyGraph.getIncomingNodeSet(simpleHNode);
847 // for (Iterator iterator3 = inNodeSet.iterator(); iterator3.hasNext();) {
848 // HNode inNode = (HNode) iterator3.next();
849 // System.out.println(" inNode=" + inNode + " combineSet="
850 // + simpleHierarchyGraph.getCombineSetByCombinationNode(inNode) + " SKELETON TO SET="
851 // + simpleHierarchyGraph.getSkeleteNodeSetReachTo(inNode));
856 // add an edge from a skeleton node to a combination node
857 for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
858 HNode inSkeletonNode = (HNode) iterator2.next();
859 // System.out.println("--inSkeletonNode=" + inSkeletonNode + " desc="
860 // + inSkeletonNode.getDescriptor());
862 if (inSkeletonNode.getDescriptor() == null) {
863 // the node is merging one...
864 srcNode = inSkeletonNode;
866 srcNode = getHNode(inSkeletonNode.getDescriptor());
868 // System.out.println("--srcNode=" + srcNode);
869 System.out.println(" ADD EDGE SRC=" + srcNode + " -> " + combinationNode);
870 addEdgeWithNoCycleCheck(srcNode, combinationNode);
873 // add an edge from the combination node to outgoing nodes
874 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
875 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
876 HNode curNode = (HNode) iterator2.next();
877 if (curNode.isCombinationNode()) {
878 Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
879 HNode outNode = getCombinationNode(combineNode);
880 addEdgeWithNoCycleCheck(combinationNode, outNode);
881 } else if (curNode.isSkeleton()) {
882 // HNode dstNode2 = getHNode(curNode.getDescriptor());
883 HNode dstNode = getCurrentHNode(curNode);
884 // System.out.println("-----curNode=" + curNode + "------->" + dstNode + " dstNode2="
886 addEdgeWithNoCycleCheck(combinationNode, dstNode);
890 // System.out.println("--");
896 public Set<HNode> getSkeleteNodeSetReachToNoTransitive(HNode node) {
898 Set<HNode> reachToSet = new HashSet<HNode>();
899 Set<HNode> visited = new HashSet<HNode>();
900 // visited.add(node);
901 recurSkeletonReachTo(node, reachToSet, visited);
904 // if a node reaches to one of elements in the reachToSet, we do not need to keep it
905 // because the node is not directly connected to the combination node
906 // removeRedundantReachToNodes(reachToSet);
908 return removeTransitivelyReachToSet(reachToSet);
909 // return reachToSet;
912 public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
914 Set<HNode> reachToSet = new HashSet<HNode>();
915 Set<HNode> visited = new HashSet<HNode>();
916 // visited.add(node);
917 recurSkeletonReachTo(node, reachToSet, visited);
920 // if a node reaches to one of elements in the reachToSet, we do not need to keep it
921 // because the node is not directly connected to the combination node
922 // removeRedundantReachToNodes(reachToSet);
925 return removeTransitivelyReachToSet(reachToSet);
926 // return reachToSet;
929 private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
931 Set<HNode> inSet = getIncomingNodeSet(node);
932 for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
933 HNode inNode = (HNode) iterator.next();
935 if (inNode.isSkeleton()) {
937 reachToSet.add(inNode);
938 } else if (!visited.contains(inNode)) {
940 recurSkeletonReachTo(inNode, reachToSet, visited);
946 public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
947 return mapHNodeToOutgoingSet;
950 public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
951 return mapHNodeToIncomingSet;
954 public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
955 mapHNodeToOutgoingSet.clear();
956 Set<HNode> keySet = in.keySet();
957 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
958 HNode key = (HNode) iterator.next();
959 Set<HNode> inSet = in.get(key);
960 Set<HNode> newSet = new HashSet<HNode>();
961 newSet.addAll(inSet);
962 mapHNodeToOutgoingSet.put(key, newSet);
966 public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
967 mapHNodeToIncomingSet.clear();
968 Set<HNode> keySet = in.keySet();
969 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
970 HNode key = (HNode) iterator.next();
971 Set<HNode> inSet = in.get(key);
972 Set<HNode> newSet = new HashSet<HNode>();
973 newSet.addAll(inSet);
974 mapHNodeToIncomingSet.put(key, newSet);
978 public void setNodeSet(Set<HNode> inSet) {
980 nodeSet.addAll(inSet);
983 public HierarchyGraph clone() {
984 HierarchyGraph clone = new HierarchyGraph();
985 clone.setDesc(getDesc());
986 clone.setName(getName());
987 clone.setNodeSet(getNodeSet());
988 clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
989 clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
990 clone.setMapDescToHNode(getMapDescToHNode());
991 clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
992 clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
993 clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
994 clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
999 public void setMapCombineNodeSetToCombinationNode(Map<Set<HNode>, HNode> in) {
1000 mapCombineNodeSetToCombinationNode = in;
1003 public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
1004 return mapMergeNodetoMergingSet;
1007 public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
1008 this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
1011 public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
1013 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1014 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1016 return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
1019 public void identifyCombinationNodes() {
1021 // 1) set combination node flag if a node combines more than one skeleton node.
1022 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1023 HNode node = (HNode) iterator.next();
1024 if (!node.isSkeleton()) {
1025 Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
1026 // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
1027 // System.out.println("ALL REACH SET=" + reachToSet);
1028 // reachToSet = removeTransitivelyReachToSet(reachToSet);
1030 Set<HNode> curReachToSet = new HashSet<HNode>();
1031 for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
1032 HNode reachSkeletonNode = (HNode) iterator2.next();
1033 curReachToSet.add(getCurrentHNode(reachSkeletonNode));
1036 // System.out.println("-curReachToSett=" + curReachToSet + " reachToSet=" + reachToSet);
1038 reachToSet = curReachToSet;
1039 // System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet + " tempSet="
1041 if (reachToSet.size() > 1) {
1042 // if (countSkeletonNodes(reachToSet) > 1) {
1043 System.out.println("\n-node=" + node + " reachToSet=" + reachToSet);
1044 System.out.println("-set combinationnode=" + node);
1045 node.setCombinationNode(true);
1046 mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
1048 // check if this node is the first node of the chain
1049 // boolean isFirstNodeOfChain = false;
1050 // Set<HNode> inNodeSet = getIncomingNodeSet(node);
1051 // for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
1052 // HNode inNode = (HNode) iterator2.next();
1053 // if (inNode.isSkeleton()) {
1054 // isFirstNodeOfChain = true;
1055 // } else if (inNode.isCombinationNode()) {
1056 // Set<HNode> inNodeReachToSet = getSkeleteNodeSetReachTo(inNode);
1057 // if (!reachToSet.equals(inNodeReachToSet)) {
1058 // isFirstNodeOfChain = true;
1063 // if (isFirstNodeOfChain) {
1064 // node.setDirectCombinationNode(true);
1065 // addFirstNodeOfChain(reachToSet, node);
1072 // 2) compute the outgoing set that needs to be directly connected from the combination node
1073 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1074 HNode node = (HNode) iterator.next();
1075 if (node.isCombinationNode()) {
1076 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1077 Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
1078 addMapCombineSetToOutgoingSet(combineSet, outSet);
1084 public void addFirstNodeOfChain(Set<HNode> combineSet, HNode firstNode) {
1086 if (!mapCombineNodeSetToFirstNodeOfChainSet.containsKey(combineSet)) {
1087 mapCombineNodeSetToFirstNodeOfChainSet.put(combineSet, new HashSet<HNode>());
1090 mapCombineNodeSetToFirstNodeOfChainSet.get(combineSet).add(firstNode);
1094 public Set<HNode> getFirstNodeOfCombinationNodeChainSet(Set<HNode> combineNodeSet) {
1095 return mapCombineNodeSetToFirstNodeOfChainSet.get(combineNodeSet);
1098 private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
1100 Set<HNode> toberemoved = new HashSet<HNode>();
1101 Set<HNode> visited = new HashSet<HNode>();
1102 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
1103 HNode node = (HNode) iterator.next();
1105 recurIsReachingTo(node, reachToSet, toberemoved, visited);
1108 Set<HNode> rSet = new HashSet<HNode>();
1109 rSet.addAll(reachToSet);
1110 rSet.removeAll(toberemoved);
1114 private void recurIsReachingTo(HNode curNode, Set<HNode> reachToSet, Set<HNode> toberemoved,
1115 Set<HNode> visited) {
1116 Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1118 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1119 HNode inNode = (HNode) iterator.next();
1120 if (reachToSet.contains(inNode)) {
1121 toberemoved.add(inNode);
1122 } else if (!visited.contains(inNode)) {
1123 visited.add(inNode);
1124 recurIsReachingTo(inNode, reachToSet, toberemoved, visited);
1130 public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
1131 return mapCombinationNodeToCombineNodeSet;
1134 public int countSkeletonNodes(Set<HNode> set) {
1137 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1138 HNode node = (HNode) iterator.next();
1139 Set<Descriptor> descSet = getDescSetOfNode(node);
1140 count += descSet.size();
1146 private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
1147 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1148 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1150 mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
1153 private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
1154 // the method returns the set of nodes that are reachable from the current node
1155 // and do not combine the same set of skeleton nodes...
1157 Set<HNode> visited = new HashSet<HNode>();
1158 Set<HNode> reachableSet = new HashSet<HNode>();
1159 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1161 recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
1163 return reachableSet;
1166 private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
1167 Set<HNode> reachableSet, Set<HNode> visited) {
1169 Set<HNode> outSet = getOutgoingNodeSet(node);
1170 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1171 HNode outNode = (HNode) iterator.next();
1173 if (outNode.isCombinationNode()) {
1174 Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
1175 if (combineSetOfOutNode.equals(combineSet)) {
1176 recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
1179 reachableSet.add(outNode);
1181 } else if (outNode.isSkeleton()) {
1182 reachableSet.add(outNode);
1189 private Set<HNode> getReachableNodeSetFrom(HNode node) {
1191 Set<HNode> reachableSet = new HashSet<HNode>();
1192 Set<HNode> visited = new HashSet<HNode>();
1194 recurReachableNodeSetFrom(node, reachableSet, visited);
1196 return reachableSet;
1199 private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
1201 Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
1202 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
1203 HNode outNode = (HNode) iterator.next();
1204 reachableSet.add(outNode);
1205 if (!visited.contains(outNode)) {
1206 visited.add(outNode);
1207 recurReachableNodeSetFrom(outNode, reachableSet, visited);
1213 public void assignUniqueIndexToNode() {
1215 // System.out.println("nodeSet=" + nodeSet);
1216 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1217 HNode node = (HNode) iterator.next();
1218 mapHNodeToUniqueIndex.put(node, idx);
1222 BASISTOPELEMENT = new HashSet<Integer>();
1223 for (int i = 1; i < idx + 1; i++) {
1224 BASISTOPELEMENT.add(i);
1228 public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1230 // assign a unique index to a node
1231 assignUniqueIndexToNode();
1233 // compute basis for each node
1234 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1235 HNode node = (HNode) iterator.next();
1237 if (notGenerateSet.contains(node)) {
1238 System.out.println("%%%SKIP =" + node);
1241 Set<Integer> basis = new HashSet<Integer>();
1242 basis.addAll(BASISTOPELEMENT);
1244 Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1245 // System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet);
1246 // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1247 // if a node is reachable from the current node
1248 // need to remove the index of the reachable node from the basis
1250 basis.remove(getHNodeIndex(node));
1251 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1252 HNode reachableNode = (HNode) iterator2.next();
1253 // System.out.println("reachableNode=" + reachableNode);
1254 // System.out.println("getHNodeIndex(reachableNode))="
1255 // + mapHNodeToUniqueIndex.get(reachableNode));
1256 int idx = getHNodeIndex(reachableNode);
1260 mapHNodeToBasis.put(node, basis);
1263 // construct the basis set
1265 BasisSet basisSet = new BasisSet();
1267 Set<HNode> keySet = mapHNodeToBasis.keySet();
1268 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1269 HNode node = (HNode) iterator.next();
1270 Set<Integer> basis = mapHNodeToBasis.get(node);
1271 basisSet.addElement(basis, node);
1278 public int getHNodeIndex(HNode node) {
1279 return mapHNodeToUniqueIndex.get(node).intValue();
1282 public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1283 return mapHNodeToUniqueIndex;
1286 public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1287 return mapHNodeToBasis;
1290 public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1292 Set<HNode> combinationNodeSet = new HashSet<HNode>();
1293 Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1294 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1295 HNode key = (HNode) iterator.next();
1297 if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1298 combinationNodeSet.add(key);
1302 return combinationNodeSet;
1305 public void writeGraph() {
1309 public void writeGraph(boolean isSimple) {
1311 String graphName = "hierarchy" + name;
1312 graphName = graphName.replaceAll("[\\W]", "");
1315 graphName += "_PAPER";
1318 // System.out.println("***graphName=" + graphName + " node siz=" + nodeSet.size());
1321 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1323 bw.write("digraph " + graphName + " {\n");
1325 Iterator<HNode> iter = nodeSet.iterator();
1327 Set<HNode> addedNodeSet = new HashSet<HNode>();
1329 while (iter.hasNext()) {
1330 HNode u = iter.next();
1332 Set<HNode> outSet = getOutgoingNodeSet(u);
1334 if (outSet.size() == 0) {
1335 if (!addedNodeSet.contains(u)) {
1339 drawNodeName(bw, u);
1341 addedNodeSet.add(u);
1344 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1345 HNode v = (HNode) iterator.next();
1346 if (!addedNodeSet.contains(u)) {
1350 drawNodeName(bw, u);
1352 addedNodeSet.add(u);
1354 if (!addedNodeSet.contains(v)) {
1358 drawNodeName(bw, v);
1360 addedNodeSet.add(v);
1362 bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1371 } catch (IOException e) {
1372 e.printStackTrace();
1376 public boolean contains(HNode node) {
1377 return nodeSet.contains(node);
1380 public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1381 return getOutgoingNodeSet(src).contains(dst);
1384 private String convertMergeSetToString(Set<HNode> mergeSet) {
1386 for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1387 HNode merged = (HNode) iterator.next();
1388 if (merged.isMergeNode()) {
1389 str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1391 str += " " + merged.getName();
1397 private void drawNodeName(BufferedWriter bw, HNode node) throws IOException {
1398 String nodeName = node.getNamePropertyString();
1399 bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1402 private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1404 if (node.isMergeNode()) {
1405 nodeName = node.getNamePropertyString();
1406 Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1407 // System.out.println("node=" + node + " mergeSet=" + mergeSet);
1408 nodeName += ":" + convertMergeSetToString(mergeSet);
1410 nodeName = node.getNamePropertyString();
1412 bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1415 public int countHopFromTopLocation(HNode node) {
1417 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1419 if (inNodeSet.size() > 0) {
1420 count = recurCountHopFromTopLocation(inNodeSet, 1);
1426 private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1429 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1430 HNode node = (HNode) iterator.next();
1431 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1432 if (inNodeSet.size() > 0) {
1433 int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1434 if (max < recurCount) {
1442 public Stack<String> computeDistance2(HNode startNode, Set<HNode> endNodeSet,
1443 HierarchyGraph scGraph, Set<HNode> combineSet) {
1445 .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
1446 Stack<String> trace = new Stack<String>();
1447 return recur_computeDistance2(startNode, endNodeSet, scGraph, 0, combineSet, trace);
1450 public Stack<String> computeDistance(HNode startNode, Set<HNode> endNodeSet,
1451 HierarchyGraph scGraph, Set<HNode> combineSet) {
1453 .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
1454 Stack<String> trace = new Stack<String>();
1455 return recur_computeDistance(startNode, endNodeSet, 0, combineSet, trace);
1458 private Stack<String> recur_computeDistance(HNode curNode, Set<HNode> endNodeSet, int count,
1459 Set<HNode> combineSet, Stack<String> trace) {
1461 if (!curNode.isSkeleton()) {
1462 if (curNode.isSharedNode()) {
1469 if (endNodeSet.contains(curNode)) {
1470 // it reaches to one of endNodeSet
1474 Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1476 int curMaxDistance = 0;
1477 Stack<String> curMaxTrace = (Stack<String>) trace.clone();
1479 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1480 HNode inNode = (HNode) iterator.next();
1483 if (inNode.isCombinationNode() && combineSet != null) {
1484 // check if inNode have the same combination set of the starting node
1485 Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
1486 if (!inNodeCombineSet.equals(combineSet)) {
1491 // System.out.println(" traverse more to" + inNode + " before-trace=" + trace);
1492 Stack<String> newTrace = (Stack<String>) trace.clone();
1493 Stack<String> curTrace =
1494 recur_computeDistance(inNode, endNodeSet, count, combineSet, newTrace);
1495 // System.out.println("curTracerTrace=" + curTrace);
1497 if (curTrace != null && curTrace.size() > curMaxDistance) {
1498 curMaxTrace = curTrace;
1499 curMaxDistance = curTrace.size();
1506 private Stack<String> recur_computeDistance2(HNode curNode, Set<HNode> endNodeSet,
1507 HierarchyGraph scGraph, int count, Set<HNode> combineSet, Stack<String> trace) {
1509 if (!curNode.isSkeleton()) {
1510 if (curNode.isSharedNode()) {
1517 System.out.println(" curNode=" + curNode + " curTrace=" + trace);
1518 // System.out.println(" curNode=" + curNode + " curSCNode="
1519 // + scGraph.getCurrentHNode(curNode) + " contains="
1520 // + endNodeSet.contains(scGraph.getCurrentHNode(curNode)));
1521 if (endNodeSet.contains(scGraph.getCurrentHNode(curNode))) {
1522 // it reaches to one of endNodeSet
1526 Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1528 int curMaxDistance = 0;
1529 Stack<String> curMaxTrace = (Stack<String>) trace.clone();
1531 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1532 HNode inNode = (HNode) iterator.next();
1535 if (inNode.isCombinationNode() && combineSet != null) {
1536 // check if inNode have the same combination set of the starting node
1537 Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
1538 if (!inNodeCombineSet.equals(combineSet)) {
1543 // Stack<String> newTrace = (Stack<String>) trace.clone();
1544 // Stack<String> curTrace =
1545 // recur_computeDistance(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
1546 // if (curTrace != null) {
1550 Set<HNode> inReachToNodeSet = getSkeleteNodeSetReachToNoTransitive(inNode);
1551 Set<HNode> inCurReachToNodeSet = new HashSet<HNode>();
1552 for (Iterator iterator2 = inReachToNodeSet.iterator(); iterator2.hasNext();) {
1553 HNode aboveNode = (HNode) iterator2.next();
1554 inCurReachToNodeSet.add(getCurrentHNode(aboveNode));
1557 if (combineSet != null || inCurReachToNodeSet.equals(endNodeSet)) {
1559 .println(" traverse to incomingNode=" + inNode + " before-trace=" + trace);
1561 Stack<String> newTrace = (Stack<String>) trace.clone();
1562 Stack<String> curTrace =
1563 recur_computeDistance2(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
1565 if (curTrace != null && curTrace.size() > curMaxDistance) {
1566 curMaxTrace = curTrace;
1567 curMaxDistance = curTrace.size();
1570 System.out.println("NOT TRAVERSE a new inNode=" + inNode + " inReachToNodeSet="
1571 + inCurReachToNodeSet);
1578 public int countNonSharedNode(HNode startNode, Set<HNode> endNodeSet) {
1579 System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
1580 return recur_countNonSharedNode(startNode, endNodeSet, 0);
1583 private int recur_countNonSharedNode(HNode startNode, Set<HNode> endNodeSet, int count) {
1585 Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
1587 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1588 HNode inNode = (HNode) iterator.next();
1589 if (endNodeSet.contains(inNode)) {
1593 if (!inNode.isSharedNode()) {
1596 return recur_countNonSharedNode2(inNode, endNodeSet, count);
1603 public int countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet) {
1604 System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
1605 return recur_countNonSharedNode2(startNode, endNodeSet, 0);
1608 private int recur_countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet, int count) {
1610 Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
1612 if (inNodeSet.size() == 0) {
1613 // it is directly connected to the TOP node
1616 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1617 HNode inNode = (HNode) iterator.next();
1618 if (endNodeSet.contains(inNode)) {
1621 if (!inNode.isSharedNode()) {
1624 return recur_countNonSharedNode2(inNode, endNodeSet, count);
1628 // System.out.println("startNode=" + startNode + " inNodeSet=" + inNodeSet);
1629 // HNode inNode = inNodeSet.iterator().next();
1633 public void removeIsolatedNodes() {
1634 Set<HNode> toberemoved = new HashSet<HNode>();
1635 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1636 HNode node = (HNode) iterator.next();
1637 if (getIncomingNodeSet(node).isEmpty() && getOutgoingNodeSet(node).isEmpty()) {
1638 toberemoved.add(node);
1641 nodeSet.removeAll(toberemoved);