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;
13 import IR.FieldDescriptor;
14 import IR.VarDescriptor;
16 public class HierarchyGraph {
23 Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
24 Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
26 Map<Descriptor, HNode> mapDescToHNode;
27 Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
28 Map<HNode, HNode> mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node
29 Map<String, HNode> mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial
31 Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
33 // data structures for a combination node
34 Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
35 Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
36 Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
37 Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
41 // for the lattice generation
42 Map<HNode, Integer> mapHNodeToUniqueIndex;
43 Map<HNode, Set<Integer>> mapHNodeToBasis;
44 Set<Integer> BASISTOPELEMENT;
46 public HierarchyGraph() {
47 mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
48 mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
49 mapHNodeToDescSet = new HashMap<HNode, Set<Descriptor>>();
50 mapDescToHNode = new HashMap<Descriptor, HNode>();
51 mapSkeletonNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
52 mapCombinationNodeToCombineNodeSet = new HashMap<HNode, Set<HNode>>();
53 mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
54 mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
55 nodeSet = new HashSet<HNode>();
57 mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
58 mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
60 mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
62 mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
64 mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
68 public Descriptor getDesc() {
72 public void setDesc(Descriptor desc) {
76 public String getName() {
80 public void setName(String name) {
84 public HierarchyGraph(Descriptor d) {
90 public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
91 return mapHNodeToDescSet;
94 public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
95 mapHNodeToDescSet.putAll(map);
98 public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
99 return mapHNodeToCurrentHNode;
102 public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
103 return mapHNodeNameToCurrentHNode;
106 public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
107 this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
110 public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
111 this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
114 public Map<Descriptor, HNode> getMapDescToHNode() {
115 return mapDescToHNode;
118 public void setMapDescToHNode(Map<Descriptor, HNode> map) {
119 mapDescToHNode.putAll(map);
122 public Set<HNode> getNodeSet() {
126 public void addEdge(HNode srcHNode, HNode dstHNode) {
128 if (!nodeSet.contains(srcHNode)) {
129 nodeSet.add(srcHNode);
132 if (!nodeSet.contains(dstHNode)) {
133 nodeSet.add(dstHNode);
136 Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
138 if (possibleCycleSet.size() > 0) {
140 if (possibleCycleSet.size() == 1) {
141 if (dstHNode.isSharedNode()) {
142 // it has already been assigned shared node.
144 dstHNode.setSharedNode(true);
149 HNode newMergeNode = mergeNodes(possibleCycleSet, false);
150 newMergeNode.setSharedNode(true);
151 System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode);
152 System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode + "\n");
154 getIncomingNodeSet(dstHNode).add(srcHNode);
155 getOutgoingNodeSet(srcHNode).add(dstHNode);
156 // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
161 public void addNode(HNode node) {
165 public void addEdge(Descriptor src, Descriptor dst) {
166 HNode srcHNode = getHNode(src);
167 HNode dstHNode = getHNode(dst);
169 addEdge(srcHNode, dstHNode);
173 public void setParamHNode(Descriptor d) {
174 getHNode(d).setSkeleton(true);
177 public HNode getHNode(Descriptor d) {
178 if (!mapDescToHNode.containsKey(d)) {
179 HNode newNode = new HNode(d);
180 if (d instanceof FieldDescriptor) {
181 newNode.setSkeleton(true);
183 mappingDescriptorToHNode(d, newNode);
184 nodeSet.add(newNode);
186 return mapDescToHNode.get(d);
189 public HNode getHNode(String name) {
190 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
191 HNode node = (HNode) iterator.next();
192 if (node.getName().equals(name)) {
199 private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
200 mapDescToHNode.put(desc, node);
201 if (!mapHNodeToDescSet.containsKey(node)) {
202 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
204 mapHNodeToDescSet.get(node).add(desc);
207 public HierarchyGraph generateSkeletonGraph() {
209 // compose a skeleton graph that only consists of fields or parameters
210 HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
211 skeletonGraph.setName(desc + "_SKELETON");
213 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
214 HNode src = (HNode) iterator.next();
215 if (src.isSkeleton()) {
216 Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
217 if (reachSet.size() > 0) {
218 for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
219 HNode dst = (HNode) iterator2.next();
220 skeletonGraph.addEdge(src, dst);
223 skeletonGraph.addNode(src);
228 skeletonGraph.setMapDescToHNode(getMapDescToHNode());
229 skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
230 skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
231 skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
233 return skeletonGraph;
237 private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
239 Set<HNode> visited = new HashSet<HNode>();
240 Set<HNode> connected = new HashSet<HNode>();
241 recurReachSkeletonSet(node, connected, visited);
246 public void removeRedundantEdges() {
248 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
249 HNode src = (HNode) iterator.next();
250 Set<HNode> connectedSet = getOutgoingNodeSet(src);
251 Set<HNode> toberemovedSet = new HashSet<HNode>();
252 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
253 HNode dst = (HNode) iterator2.next();
254 Set<HNode> otherNeighborSet = new HashSet<HNode>();
255 otherNeighborSet.addAll(connectedSet);
256 otherNeighborSet.remove(dst);
257 for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
258 HNode neighbor = (HNode) iterator3.next();
259 if (reachTo(neighbor, dst, new HashSet<HNode>())) {
260 toberemovedSet.add(dst);
264 if (toberemovedSet.size() > 0) {
265 connectedSet.removeAll(toberemovedSet);
267 for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
268 HNode node = (HNode) iterator2.next();
269 getIncomingNodeSet(node).remove(src);
277 public void simplifyHierarchyGraph() {
278 removeRedundantEdges();
279 combineRedundantNodes(false);
282 public void simplifySkeletonCombinationHierarchyGraph() {
283 removeRedundantEdges();
284 combineRedundantNodes(true);
287 public void combineRedundantNodes(boolean onlyCombinationNodes) {
288 // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
289 boolean isUpdated = false;
291 isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes);
295 public Set<HNode> getIncomingNodeSet(HNode node) {
296 if (!mapHNodeToIncomingSet.containsKey(node)) {
297 mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
299 return mapHNodeToIncomingSet.get(node);
302 public Set<HNode> getOutgoingNodeSet(HNode node) {
303 if (!mapHNodeToOutgoingSet.containsKey(node)) {
304 mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
306 return mapHNodeToOutgoingSet.get(node);
309 private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes) {
310 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
311 HNode node1 = (HNode) iterator.next();
313 if ((onlyCombinationNodes && (!node1.isCombinationNode()))
314 || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
318 Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
319 Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
321 for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
322 HNode node2 = (HNode) iterator2.next();
324 if ((onlyCombinationNodes && (!node2.isCombinationNode()))
325 || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
329 if (!isEligibleForMerging(node1, node2)) {
333 if (!node1.equals(node2)) {
335 Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
336 Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
338 if (incomingNodeSet1.equals(incomingNodeSet2)
339 && outgoingNodeSet1.equals(outgoingNodeSet2)) {
340 // need to merge node1 and node2
342 Set<HNode> mergeSet = new HashSet<HNode>();
345 mergeNodes(mergeSet, onlyCombinationNodes);
356 private boolean isEligibleForMerging(HNode node1, HNode node2) {
358 System.out.println("********isEligibleForMerging=" + node1 + " " + node2);
360 if (node1.isSharedNode() || node2.isSharedNode()) {
362 // if either of nodes is a shared node,
363 // all descriptors of node1 & node2 should have a primitive type
365 Set<Descriptor> descSet = new HashSet<Descriptor>();
366 descSet.addAll(getDescSetOfNode(node1));
367 descSet.addAll(getDescSetOfNode(node2));
369 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
370 Descriptor desc = (Descriptor) iterator.next();
371 if (!LocationInference.isPrimitive(desc)) {
375 System.out.println("******** true");
381 private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
382 getIncomingNodeSet(dstHNode).add(srcHNode);
383 getOutgoingNodeSet(srcHNode).add(dstHNode);
384 System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
387 private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
389 Set<HNode> incomingNodeSet = new HashSet<HNode>();
390 Set<HNode> outgoingNodeSet = new HashSet<HNode>();
392 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
393 HNode node = (HNode) iterator.next();
394 incomingNodeSet.addAll(getIncomingNodeSet(node));
395 outgoingNodeSet.addAll(getOutgoingNodeSet(node));
399 boolean isMergeNode = false;
400 if (onlyCombinationNodes) {
401 nodeName = "Comb" + (LocationInference.locSeed++);
403 nodeName = "Node" + (LocationInference.locSeed++);
406 HNode newMergeNode = new HNode(nodeName);
407 newMergeNode.setMergeNode(isMergeNode);
409 nodeSet.add(newMergeNode);
410 nodeSet.removeAll(set);
412 // if the input set contains a skeleton node, need to set a new merge node as skeleton also
413 boolean hasSkeleton = false;
414 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
415 HNode inNode = (HNode) iterator.next();
416 if (inNode.isSkeleton()) {
421 System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set
422 + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
423 newMergeNode.setSkeleton(hasSkeleton);
425 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
426 HNode node = (HNode) iterator.next();
427 Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
428 for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
429 Descriptor desc = (Descriptor) iterator2.next();
430 mappingDescriptorToHNode(desc, newMergeNode);
434 for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
435 HNode inNode = (HNode) iterator.next();
436 Set<HNode> outSet = getOutgoingNodeSet(inNode);
437 outSet.removeAll(set);
438 if (!set.contains(inNode)) {
439 addEdgeWithNoCycleCheck(inNode, newMergeNode);
443 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
444 HNode outNode = (HNode) iterator.next();
445 Set<HNode> inSet = getIncomingNodeSet(outNode);
446 inSet.removeAll(set);
447 if (!set.contains(outNode)) {
448 addEdgeWithNoCycleCheck(newMergeNode, outNode);
452 Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
453 for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
454 HNode merged = iter.next();
455 if (merged.isSkeleton()) {
456 mergedSkeletonNode.add(merged);
460 // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
461 // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
462 mapMergeNodetoMergingSet.put(newMergeNode, set);
463 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
464 HNode mergedNode = (HNode) iterator.next();
465 addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
467 System.out.println("###mergedSkeletonNode=" + mergedSkeletonNode);
468 System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
470 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
471 HNode hNode = (HNode) iterator.next();
472 System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
478 private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
479 if (curNode.isMergeNode()) {
480 Set<HNode> mergingSet = getMergingSet(curNode);
481 mergingSet.add(curNode);
482 System.out.println("addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
484 for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
485 HNode mergingNode = (HNode) iterator.next();
486 mapHNodeToCurrentHNode.put(mergingNode, newNode);
487 mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
490 mapHNodeToCurrentHNode.put(curNode, newNode);
491 mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
495 public HNode getCurrentHNode(HNode node) {
496 if (!mapHNodeToCurrentHNode.containsKey(node)) {
497 mapHNodeToCurrentHNode.put(node, node);
499 return mapHNodeToCurrentHNode.get(node);
502 public HNode getCurrentHNode(String nodeName) {
503 return mapHNodeNameToCurrentHNode.get(nodeName);
506 private Set<HNode> getMergingSet(HNode mergeNode) {
507 Set<HNode> mergingSet = new HashSet<HNode>();
508 Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
509 for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
510 HNode node = (HNode) iterator.next();
511 if (node.isMergeNode()) {
512 mergingSet.add(node);
513 mergingSet.addAll(getMergingSet(node));
515 mergingSet.add(node);
521 public Set<Descriptor> getDescSetOfNode(HNode node) {
522 if (!mapHNodeToDescSet.containsKey(node)) {
523 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
525 return mapHNodeToDescSet.get(node);
528 private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
529 Set<HNode> connectedSet = getOutgoingNodeSet(src);
530 for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
531 HNode n = iterator.next();
535 if (!visited.contains(n)) {
537 if (reachTo(n, dst, visited)) {
545 private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
547 Set<HNode> outSet = getOutgoingNodeSet(node);
548 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
549 HNode outNode = (HNode) iterator.next();
551 if (outNode.isSkeleton()) {
552 connected.add(outNode);
553 } else if (!visited.contains(outNode)) {
554 visited.add(outNode);
555 recurReachSkeletonSet(outNode, connected, visited);
561 public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
562 Set<HNode> combinationNodeSet) {
563 Set<HNode> reachable = new HashSet<HNode>();
564 Set<HNode> visited = new HashSet<HNode>();
566 recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
570 public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
571 Set<HNode> reachable, Set<HNode> combinationNodeSet) {
573 Set<HNode> outSet = getOutgoingNodeSet(node);
574 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
575 HNode out = (HNode) iterator.next();
577 if (!visited.contains(out)) {
579 if (out.isSkeleton()) {
581 } else if (out.isCombinationNode()) {
582 if (combinationNodeSet == null) {
584 } else if (!combinationNodeSet.contains(out)) {
587 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
591 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
601 public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
602 Set<HNode> visited = new HashSet<HNode>();
603 return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
606 public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
608 Set<HNode> outSet = getOutgoingNodeSet(node);
609 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
610 HNode out = (HNode) iterator.next();
611 // if (!visited.contains(out)) {
612 if (out.isCombinationNode() || out.isSkeleton()) {
616 return getDirectlyReachableSkeletonCombinationNodeFrom(out);
624 public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
625 // if an edge from src to dst introduces a new cycle flow,
626 // the method returns the set of elements consisting of the cycle
627 Set<HNode> cycleNodeSet = new HashSet<HNode>();
628 // if the dst node reaches to the src node, the new relation
629 // introduces a cycle to the lattice
630 if (dst.equals(src)) {
631 cycleNodeSet.add(dst);
632 cycleNodeSet.add(src);
633 } else if (reachTo(dst, src)) {
634 cycleNodeSet.add(dst);
635 cycleNodeSet.add(src);
636 getInBetweenElements(dst, src, cycleNodeSet);
641 private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
642 Set<HNode> connectedSet = getOutgoingNodeSet(start);
643 for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
644 HNode cur = (HNode) iterator.next();
645 if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
647 getInBetweenElements(cur, end, nodeSet);
652 public boolean reachTo(HNode node1, HNode node2) {
653 return reachTo(node1, node2, new HashSet<HNode>());
656 public Set<HNode> getCombineSetByCombinationNode(HNode node) {
657 if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
658 mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
660 return mapCombinationNodeToCombineNodeSet.get(node);
663 public HNode getCombinationNode(Set<HNode> combineSet) {
664 if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
665 String name = "COMB" + (LocationInference.locSeed++);
666 HNode node = new HNode(name);
667 node.setCombinationNode(true);
669 mapCombineNodeSetToCombinationNode.put(combineSet, node);
670 mapCombinationNodeToCombineNodeSet.put(node, combineSet);
673 return mapCombineNodeSetToCombinationNode.get(combineSet);
676 public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
677 return mapCombineNodeSetToCombinationNode;
680 public Set<Set<HNode>> getCombineNodeSet() {
681 return mapCombineNodeSetToOutgoingNodeSet.keySet();
684 public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
685 // add a new combination node where parameter/field flows are actually combined.
687 simpleHierarchyGraph.identifyCombinationNodes();
689 Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
690 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
691 Set<HNode> combineSet = (Set<HNode>) iterator.next();
692 System.out.println("--combineSet=" + combineSet);
693 HNode combinationNode = getCombinationNode(combineSet);
694 System.out.println("--combinationNode=" + combinationNode);
695 // add an edge from a skeleton node to a combination node
696 for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
697 HNode inSkeletonNode = (HNode) iterator2.next();
698 // System.out.println("--inSkeletonNode=" + inSkeletonNode + " desc="
699 // + inSkeletonNode.getDescriptor());
701 if (inSkeletonNode.getDescriptor() == null) {
702 // the node is merging one...
703 srcNode = inSkeletonNode;
705 srcNode = getHNode(inSkeletonNode.getDescriptor());
707 // System.out.println("--srcNode=" + srcNode);
708 addEdgeWithNoCycleCheck(srcNode, combinationNode);
711 // add an edge from the combination node to outgoing nodes
712 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
713 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
714 HNode curNode = (HNode) iterator2.next();
715 if (curNode.isCombinationNode()) {
716 Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
717 HNode outNode = getCombinationNode(combineNode);
718 addEdgeWithNoCycleCheck(combinationNode, outNode);
719 } else if (curNode.isSkeleton()) {
720 // HNode dstNode2 = getHNode(curNode.getDescriptor());
721 HNode dstNode = getCurrentHNode(curNode);
722 // System.out.println("-----curNode=" + curNode + "------->" + dstNode + " dstNode2="
724 addEdgeWithNoCycleCheck(combinationNode, dstNode);
728 System.out.println("--");
734 private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
735 if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
736 // need to create a new combination node
737 String nodeName = "Comb" + (LocationInference.locSeed++);
738 HNode newCombinationNode = new HNode(nodeName);
739 newCombinationNode.setCombinationNode(true);
741 nodeSet.add(newCombinationNode);
742 mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
744 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
745 HNode reachToNode = (HNode) iterator.next();
746 addEdge(reachToNode, newCombinationNode);
751 HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
752 for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
753 HNode reachableNode = (HNode) iterator.next();
754 addEdge(combinationNode, reachableNode);
759 private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
761 Set<HNode> reachToSet = new HashSet<HNode>();
762 Set<HNode> visited = new HashSet<HNode>();
763 recurSkeletonReachTo(node, reachToSet, visited);
765 // if a node reaches to one of elements in the reachToSet, we do not need to keep it
766 // because the node is not directly connected to the combination node
768 removeRedundantReachToNodes(reachToSet);
773 private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
775 Set<HNode> toberemoved = new HashSet<HNode>();
776 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
777 HNode cur = (HNode) iterator.next();
779 for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
780 HNode dst = (HNode) iterator2.next();
781 if (!cur.equals(dst) && reachTo(cur, dst)) {
783 toberemoved.add(cur);
787 reachToSet.removeAll(toberemoved);
790 private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
792 Set<HNode> inSet = getIncomingNodeSet(node);
793 for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
794 HNode inNode = (HNode) iterator.next();
796 if (inNode.isSkeleton()) {
797 reachToSet.add(inNode);
798 } else if (!visited.contains(inNode)) {
800 recurSkeletonReachTo(inNode, reachToSet, visited);
806 public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
807 return mapHNodeToOutgoingSet;
810 public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
811 return mapHNodeToIncomingSet;
814 public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
815 mapHNodeToOutgoingSet.clear();
816 Set<HNode> keySet = in.keySet();
817 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
818 HNode key = (HNode) iterator.next();
819 Set<HNode> inSet = in.get(key);
820 Set<HNode> newSet = new HashSet<HNode>();
821 newSet.addAll(inSet);
822 mapHNodeToOutgoingSet.put(key, newSet);
826 public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
827 mapHNodeToIncomingSet.clear();
828 Set<HNode> keySet = in.keySet();
829 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
830 HNode key = (HNode) iterator.next();
831 Set<HNode> inSet = in.get(key);
832 Set<HNode> newSet = new HashSet<HNode>();
833 newSet.addAll(inSet);
834 mapHNodeToIncomingSet.put(key, newSet);
838 public void setNodeSet(Set<HNode> inSet) {
840 nodeSet.addAll(inSet);
843 public HierarchyGraph clone() {
844 HierarchyGraph clone = new HierarchyGraph();
845 clone.setDesc(getDesc());
846 clone.setName(getName());
847 clone.setNodeSet(getNodeSet());
848 clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
849 clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
850 clone.setMapDescToHNode(getMapDescToHNode());
851 clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
852 clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
853 clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
854 clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
859 public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
860 return mapMergeNodetoMergingSet;
863 public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
864 this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
867 public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
869 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
870 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
872 return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
875 public void identifyCombinationNodes() {
877 // 1) set combination node flag if a node combines more than one skeleton node.
878 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
879 HNode node = (HNode) iterator.next();
880 if (!node.isSkeleton()) {
881 Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
882 if (reachToSet.size() > 1) {
883 // if (countSkeletonNodes(reachToSet) > 1) {
884 System.out.println("-node=" + node + " reachToSet=" + reachToSet);
885 System.out.println("-set combinationnode=" + node);
886 node.setCombinationNode(true);
887 mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
892 // 2) compute the outgoing set that needs to be directly connected from the combination node
893 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
894 HNode node = (HNode) iterator.next();
895 if (node.isCombinationNode()) {
896 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
897 Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
898 addMapCombineSetToOutgoingSet(combineSet, outSet);
904 public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
905 return mapCombinationNodeToCombineNodeSet;
908 public int countSkeletonNodes(Set<HNode> set) {
911 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
912 HNode node = (HNode) iterator.next();
913 Set<Descriptor> descSet = getDescSetOfNode(node);
914 count += descSet.size();
920 private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
921 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
922 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
924 mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
927 private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
928 // the method returns the set of nodes that are reachable from the current node
929 // and do not combine the same set of skeleton nodes...
931 Set<HNode> visited = new HashSet<HNode>();
932 Set<HNode> reachableSet = new HashSet<HNode>();
933 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
935 recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
940 private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
941 Set<HNode> reachableSet, Set<HNode> visited) {
943 Set<HNode> outSet = getOutgoingNodeSet(node);
944 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
945 HNode outNode = (HNode) iterator.next();
947 if (outNode.isCombinationNode()) {
948 Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
949 if (combineSetOfOutNode.equals(combineSet)) {
950 recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
953 reachableSet.add(outNode);
955 } else if (outNode.isSkeleton()) {
956 reachableSet.add(outNode);
963 private Set<HNode> getReachableNodeSetFrom(HNode node) {
965 Set<HNode> reachableSet = new HashSet<HNode>();
966 Set<HNode> visited = new HashSet<HNode>();
968 recurReachableNodeSetFrom(node, reachableSet, visited);
973 private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
975 Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
976 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
977 HNode outNode = (HNode) iterator.next();
978 reachableSet.add(outNode);
979 if (!visited.contains(outNode)) {
980 visited.add(outNode);
981 recurReachableNodeSetFrom(outNode, reachableSet, visited);
987 public void assignUniqueIndexToNode() {
989 System.out.println("nodeSet=" + nodeSet);
990 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
991 HNode node = (HNode) iterator.next();
992 mapHNodeToUniqueIndex.put(node, idx);
996 BASISTOPELEMENT = new HashSet<Integer>();
997 for (int i = 1; i < idx + 1; i++) {
998 BASISTOPELEMENT.add(i);
1002 public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1004 // assign a unique index to a node
1005 assignUniqueIndexToNode();
1007 // compute basis for each node
1008 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1009 HNode node = (HNode) iterator.next();
1011 if (notGenerateSet.contains(node)) {
1012 System.out.println("%%%SKIP =" + node);
1015 Set<Integer> basis = new HashSet<Integer>();
1016 basis.addAll(BASISTOPELEMENT);
1018 Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1019 System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet);
1020 System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1021 // if a node is reachable from the current node
1022 // need to remove the index of the reachable node from the basis
1024 basis.remove(getHNodeIndex(node));
1025 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1026 HNode reachableNode = (HNode) iterator2.next();
1027 System.out.println("reachableNode=" + reachableNode);
1028 System.out.println("getHNodeIndex(reachableNode))="
1029 + mapHNodeToUniqueIndex.get(reachableNode));
1030 int idx = getHNodeIndex(reachableNode);
1034 mapHNodeToBasis.put(node, basis);
1037 // construct the basis set
1039 BasisSet basisSet = new BasisSet();
1041 Set<HNode> keySet = mapHNodeToBasis.keySet();
1042 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1043 HNode node = (HNode) iterator.next();
1044 Set<Integer> basis = mapHNodeToBasis.get(node);
1045 basisSet.addElement(basis, node);
1052 public int getHNodeIndex(HNode node) {
1053 return mapHNodeToUniqueIndex.get(node).intValue();
1056 public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1057 return mapHNodeToUniqueIndex;
1060 public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1061 return mapHNodeToBasis;
1064 public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1066 Set<HNode> combinationNodeSet = new HashSet<HNode>();
1067 Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1068 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1069 HNode key = (HNode) iterator.next();
1071 if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1072 combinationNodeSet.add(key);
1076 return combinationNodeSet;
1079 public void writeGraph() {
1081 String graphName = "hierarchy" + name;
1082 graphName = graphName.replaceAll("[\\W]", "");
1085 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1087 bw.write("digraph " + graphName + " {\n");
1089 Iterator<HNode> iter = nodeSet.iterator();
1091 Set<HNode> addedNodeSet = new HashSet<HNode>();
1093 while (iter.hasNext()) {
1094 HNode u = iter.next();
1096 Set<HNode> outSet = getOutgoingNodeSet(u);
1098 if (outSet.size() == 0) {
1099 if (!addedNodeSet.contains(u)) {
1101 addedNodeSet.add(u);
1104 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1105 HNode v = (HNode) iterator.next();
1106 if (!addedNodeSet.contains(u)) {
1108 addedNodeSet.add(u);
1110 if (!addedNodeSet.contains(v)) {
1112 addedNodeSet.add(v);
1114 bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1123 } catch (IOException e) {
1124 e.printStackTrace();
1128 public boolean contains(HNode node) {
1129 return nodeSet.contains(node);
1132 public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1133 return getOutgoingNodeSet(src).contains(dst);
1136 private String convertMergeSetToString(Set<HNode> mergeSet) {
1138 for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1139 HNode merged = (HNode) iterator.next();
1140 if (merged.isMergeNode()) {
1141 str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1143 str += " " + merged.getName();
1149 private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1151 if (node.isMergeNode()) {
1152 nodeName = node.getNamePropertyString();
1153 Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1154 nodeName += ":" + convertMergeSetToString(mergeSet);
1156 nodeName = node.getNamePropertyString();
1158 bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1161 public int countHopFromTopLocation(HNode node) {
1163 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1165 if (inNodeSet.size() > 0) {
1166 count = recurCountHopFromTopLocation(inNodeSet, 1);
1172 private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1175 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1176 HNode node = (HNode) iterator.next();
1177 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1178 if (inNodeSet.size() > 0) {
1179 int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1180 if (max < recurCount) {