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) {
167 if (src.equals(LocationInference.LITERALDESC)) {
168 // in this case, we do not need to add a source hnode
169 // just add a destination hnode
172 HNode srcHNode = getHNode(src);
173 HNode dstHNode = getHNode(dst);
174 addEdge(srcHNode, dstHNode);
179 public void setParamHNode(Descriptor d) {
180 getHNode(d).setSkeleton(true);
183 public HNode getHNode(Descriptor d) {
184 if (!mapDescToHNode.containsKey(d)) {
185 HNode newNode = new HNode(d);
187 if (d instanceof FieldDescriptor) {
188 newNode.setSkeleton(true);
191 String symbol = d.getSymbol();
192 if (symbol.startsWith(LocationInference.PCLOC) || symbol.startsWith(LocationInference.RLOC)) {
193 newNode.setSkeleton(true);
196 mappingDescriptorToHNode(d, newNode);
197 nodeSet.add(newNode);
199 return mapDescToHNode.get(d);
202 public HNode getHNode(String name) {
203 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
204 HNode node = (HNode) iterator.next();
205 if (node.getName().equals(name)) {
212 private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
213 mapDescToHNode.put(desc, node);
214 if (!mapHNodeToDescSet.containsKey(node)) {
215 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
217 mapHNodeToDescSet.get(node).add(desc);
220 public HierarchyGraph generateSkeletonGraph() {
222 // compose a skeleton graph that only consists of fields or parameters
223 HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
224 skeletonGraph.setName(desc + "_SKELETON");
226 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
227 HNode src = (HNode) iterator.next();
228 if (src.isSkeleton()) {
229 Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
230 if (reachSet.size() > 0) {
231 for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
232 HNode dst = (HNode) iterator2.next();
233 skeletonGraph.addEdge(src, dst);
236 skeletonGraph.addNode(src);
241 skeletonGraph.setMapDescToHNode(getMapDescToHNode());
242 skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
243 skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
244 skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
246 return skeletonGraph;
250 private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
252 Set<HNode> visited = new HashSet<HNode>();
253 Set<HNode> connected = new HashSet<HNode>();
254 recurReachSkeletonSet(node, connected, visited);
259 public void removeRedundantEdges() {
261 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
262 HNode src = (HNode) iterator.next();
263 Set<HNode> connectedSet = getOutgoingNodeSet(src);
264 Set<HNode> toberemovedSet = new HashSet<HNode>();
265 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
266 HNode dst = (HNode) iterator2.next();
267 Set<HNode> otherNeighborSet = new HashSet<HNode>();
268 otherNeighborSet.addAll(connectedSet);
269 otherNeighborSet.remove(dst);
270 for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
271 HNode neighbor = (HNode) iterator3.next();
272 if (reachTo(neighbor, dst, new HashSet<HNode>())) {
273 toberemovedSet.add(dst);
277 if (toberemovedSet.size() > 0) {
278 connectedSet.removeAll(toberemovedSet);
280 for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
281 HNode node = (HNode) iterator2.next();
282 getIncomingNodeSet(node).remove(src);
290 public void simplifyHierarchyGraph() {
291 removeRedundantEdges();
292 combineRedundantNodes(false);
295 public void simplifySkeletonCombinationHierarchyGraph() {
296 removeRedundantEdges();
297 combineRedundantNodes(true);
300 public void combineRedundantNodes(boolean onlyCombinationNodes) {
301 // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
302 boolean isUpdated = false;
304 isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes);
308 public Set<HNode> getIncomingNodeSet(HNode node) {
309 if (!mapHNodeToIncomingSet.containsKey(node)) {
310 mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
312 return mapHNodeToIncomingSet.get(node);
315 public Set<HNode> getOutgoingNodeSet(HNode node) {
316 if (!mapHNodeToOutgoingSet.containsKey(node)) {
317 mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
319 return mapHNodeToOutgoingSet.get(node);
322 private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes) {
323 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
324 HNode node1 = (HNode) iterator.next();
326 if ((onlyCombinationNodes && (!node1.isCombinationNode()))
327 || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
331 Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
332 Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
334 for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
335 HNode node2 = (HNode) iterator2.next();
337 if ((onlyCombinationNodes && (!node2.isCombinationNode()))
338 || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
342 if (!isEligibleForMerging(node1, node2)) {
346 if (!node1.equals(node2)) {
348 Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
349 Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
351 if (incomingNodeSet1.equals(incomingNodeSet2)
352 && outgoingNodeSet1.equals(outgoingNodeSet2)) {
353 // need to merge node1 and node2
355 Set<HNode> mergeSet = new HashSet<HNode>();
358 mergeNodes(mergeSet, onlyCombinationNodes);
369 private boolean isEligibleForMerging(HNode node1, HNode node2) {
371 if (node1.isSharedNode() || node2.isSharedNode()) {
373 // if either of nodes is a shared node,
374 // all descriptors of node1 & node2 should have a primitive type
376 Set<Descriptor> descSet = new HashSet<Descriptor>();
377 descSet.addAll(getDescSetOfNode(node1));
378 descSet.addAll(getDescSetOfNode(node2));
380 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
381 Descriptor desc = (Descriptor) iterator.next();
382 if (!LocationInference.isPrimitive(desc)) {
391 private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
392 getIncomingNodeSet(dstHNode).add(srcHNode);
393 getOutgoingNodeSet(srcHNode).add(dstHNode);
394 System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
397 private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
399 Set<HNode> incomingNodeSet = new HashSet<HNode>();
400 Set<HNode> outgoingNodeSet = new HashSet<HNode>();
402 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
403 HNode node = (HNode) iterator.next();
404 incomingNodeSet.addAll(getIncomingNodeSet(node));
405 outgoingNodeSet.addAll(getOutgoingNodeSet(node));
409 boolean isMergeNode = false;
410 if (onlyCombinationNodes) {
411 nodeName = "Comb" + (LocationInference.locSeed++);
413 nodeName = "Node" + (LocationInference.locSeed++);
416 HNode newMergeNode = new HNode(nodeName);
417 newMergeNode.setMergeNode(isMergeNode);
419 nodeSet.add(newMergeNode);
420 nodeSet.removeAll(set);
422 // if the input set contains a skeleton node, need to set a new merge node as skeleton also
423 boolean hasSkeleton = false;
424 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
425 HNode inNode = (HNode) iterator.next();
426 if (inNode.isSkeleton()) {
431 System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set
432 + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
433 newMergeNode.setSkeleton(hasSkeleton);
435 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
436 HNode node = (HNode) iterator.next();
437 Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
438 for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
439 Descriptor desc = (Descriptor) iterator2.next();
440 mappingDescriptorToHNode(desc, newMergeNode);
444 for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
445 HNode inNode = (HNode) iterator.next();
446 Set<HNode> outSet = getOutgoingNodeSet(inNode);
447 outSet.removeAll(set);
448 if (!set.contains(inNode)) {
449 addEdgeWithNoCycleCheck(inNode, newMergeNode);
453 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
454 HNode outNode = (HNode) iterator.next();
455 Set<HNode> inSet = getIncomingNodeSet(outNode);
456 inSet.removeAll(set);
457 if (!set.contains(outNode)) {
458 addEdgeWithNoCycleCheck(newMergeNode, outNode);
462 Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
463 for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
464 HNode merged = iter.next();
465 if (merged.isSkeleton()) {
466 mergedSkeletonNode.add(merged);
470 // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
471 // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
472 mapMergeNodetoMergingSet.put(newMergeNode, set);
473 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
474 HNode mergedNode = (HNode) iterator.next();
475 addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
477 System.out.println("###mergedSkeletonNode=" + mergedSkeletonNode);
478 System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
480 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
481 HNode hNode = (HNode) iterator.next();
482 System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
488 private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
489 if (curNode.isMergeNode()) {
490 Set<HNode> mergingSet = getMergingSet(curNode);
491 mergingSet.add(curNode);
492 System.out.println("addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
494 for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
495 HNode mergingNode = (HNode) iterator.next();
496 mapHNodeToCurrentHNode.put(mergingNode, newNode);
497 mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
500 mapHNodeToCurrentHNode.put(curNode, newNode);
501 mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
505 public HNode getCurrentHNode(HNode node) {
506 if (!mapHNodeToCurrentHNode.containsKey(node)) {
507 mapHNodeToCurrentHNode.put(node, node);
509 return mapHNodeToCurrentHNode.get(node);
512 public HNode getCurrentHNode(String nodeName) {
513 return mapHNodeNameToCurrentHNode.get(nodeName);
516 private Set<HNode> getMergingSet(HNode mergeNode) {
517 Set<HNode> mergingSet = new HashSet<HNode>();
518 Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
519 for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
520 HNode node = (HNode) iterator.next();
521 if (node.isMergeNode()) {
522 mergingSet.add(node);
523 mergingSet.addAll(getMergingSet(node));
525 mergingSet.add(node);
531 public Set<Descriptor> getDescSetOfNode(HNode node) {
532 if (!mapHNodeToDescSet.containsKey(node)) {
533 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
535 return mapHNodeToDescSet.get(node);
538 private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
539 Set<HNode> connectedSet = getOutgoingNodeSet(src);
540 for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
541 HNode n = iterator.next();
545 if (!visited.contains(n)) {
547 if (reachTo(n, dst, visited)) {
555 private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
557 Set<HNode> outSet = getOutgoingNodeSet(node);
558 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
559 HNode outNode = (HNode) iterator.next();
561 if (outNode.isSkeleton()) {
562 connected.add(outNode);
563 } else if (!visited.contains(outNode)) {
564 visited.add(outNode);
565 recurReachSkeletonSet(outNode, connected, visited);
571 public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
572 Set<HNode> combinationNodeSet) {
573 Set<HNode> reachable = new HashSet<HNode>();
574 Set<HNode> visited = new HashSet<HNode>();
576 recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
580 public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
581 Set<HNode> reachable, Set<HNode> combinationNodeSet) {
583 Set<HNode> outSet = getOutgoingNodeSet(node);
584 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
585 HNode out = (HNode) iterator.next();
587 if (!visited.contains(out)) {
589 if (out.isSkeleton()) {
591 } else if (out.isCombinationNode()) {
592 if (combinationNodeSet == null) {
594 } else if (!combinationNodeSet.contains(out)) {
597 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
601 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
611 public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
612 Set<HNode> visited = new HashSet<HNode>();
613 return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
616 public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
618 Set<HNode> outSet = getOutgoingNodeSet(node);
619 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
620 HNode out = (HNode) iterator.next();
621 // if (!visited.contains(out)) {
622 if (out.isCombinationNode() || out.isSkeleton()) {
626 return getDirectlyReachableSkeletonCombinationNodeFrom(out);
634 public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
635 // if an edge from src to dst introduces a new cycle flow,
636 // the method returns the set of elements consisting of the cycle
637 Set<HNode> cycleNodeSet = new HashSet<HNode>();
638 // if the dst node reaches to the src node, the new relation
639 // introduces a cycle to the lattice
640 if (dst.equals(src)) {
641 cycleNodeSet.add(dst);
642 cycleNodeSet.add(src);
643 } else if (reachTo(dst, src)) {
644 cycleNodeSet.add(dst);
645 cycleNodeSet.add(src);
646 getInBetweenElements(dst, src, cycleNodeSet);
651 private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
652 Set<HNode> connectedSet = getOutgoingNodeSet(start);
653 for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
654 HNode cur = (HNode) iterator.next();
655 if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
657 getInBetweenElements(cur, end, nodeSet);
662 public boolean reachTo(HNode node1, HNode node2) {
663 return reachTo(node1, node2, new HashSet<HNode>());
666 public Set<HNode> getCombineSetByCombinationNode(HNode node) {
667 if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
668 mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
670 return mapCombinationNodeToCombineNodeSet.get(node);
673 public HNode getCombinationNode(Set<HNode> combineSet) {
674 if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
675 String name = "COMB" + (LocationInference.locSeed++);
676 HNode node = new HNode(name);
677 node.setCombinationNode(true);
679 mapCombineNodeSetToCombinationNode.put(combineSet, node);
680 mapCombinationNodeToCombineNodeSet.put(node, combineSet);
683 return mapCombineNodeSetToCombinationNode.get(combineSet);
686 public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
687 return mapCombineNodeSetToCombinationNode;
690 public Set<Set<HNode>> getCombineNodeSet() {
691 return mapCombineNodeSetToOutgoingNodeSet.keySet();
694 public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
695 // add a new combination node where parameter/field flows are actually combined.
697 simpleHierarchyGraph.identifyCombinationNodes();
699 Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
700 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
701 Set<HNode> combineSet = (Set<HNode>) iterator.next();
702 System.out.println("--combineSet=" + combineSet);
703 HNode combinationNode = getCombinationNode(combineSet);
704 System.out.println("--combinationNode=" + combinationNode);
705 // add an edge from a skeleton node to a combination node
706 for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
707 HNode inSkeletonNode = (HNode) iterator2.next();
708 // System.out.println("--inSkeletonNode=" + inSkeletonNode + " desc="
709 // + inSkeletonNode.getDescriptor());
711 if (inSkeletonNode.getDescriptor() == null) {
712 // the node is merging one...
713 srcNode = inSkeletonNode;
715 srcNode = getHNode(inSkeletonNode.getDescriptor());
717 // System.out.println("--srcNode=" + srcNode);
718 addEdgeWithNoCycleCheck(srcNode, combinationNode);
721 // add an edge from the combination node to outgoing nodes
722 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
723 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
724 HNode curNode = (HNode) iterator2.next();
725 if (curNode.isCombinationNode()) {
726 Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
727 HNode outNode = getCombinationNode(combineNode);
728 addEdgeWithNoCycleCheck(combinationNode, outNode);
729 } else if (curNode.isSkeleton()) {
730 // HNode dstNode2 = getHNode(curNode.getDescriptor());
731 HNode dstNode = getCurrentHNode(curNode);
732 // System.out.println("-----curNode=" + curNode + "------->" + dstNode + " dstNode2="
734 addEdgeWithNoCycleCheck(combinationNode, dstNode);
738 System.out.println("--");
744 private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
745 if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
746 // need to create a new combination node
747 String nodeName = "Comb" + (LocationInference.locSeed++);
748 HNode newCombinationNode = new HNode(nodeName);
749 newCombinationNode.setCombinationNode(true);
751 nodeSet.add(newCombinationNode);
752 mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
754 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
755 HNode reachToNode = (HNode) iterator.next();
756 addEdge(reachToNode, newCombinationNode);
761 HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
762 for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
763 HNode reachableNode = (HNode) iterator.next();
764 addEdge(combinationNode, reachableNode);
769 private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
771 Set<HNode> reachToSet = new HashSet<HNode>();
772 Set<HNode> visited = new HashSet<HNode>();
773 recurSkeletonReachTo(node, reachToSet, visited);
775 // if a node reaches to one of elements in the reachToSet, we do not need to keep it
776 // because the node is not directly connected to the combination node
778 removeRedundantReachToNodes(reachToSet);
783 private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
785 Set<HNode> toberemoved = new HashSet<HNode>();
786 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
787 HNode cur = (HNode) iterator.next();
789 for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
790 HNode dst = (HNode) iterator2.next();
791 if (!cur.equals(dst) && reachTo(cur, dst)) {
793 toberemoved.add(cur);
797 reachToSet.removeAll(toberemoved);
800 private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
802 Set<HNode> inSet = getIncomingNodeSet(node);
803 for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
804 HNode inNode = (HNode) iterator.next();
806 if (inNode.isSkeleton()) {
807 reachToSet.add(inNode);
808 } else if (!visited.contains(inNode)) {
810 recurSkeletonReachTo(inNode, reachToSet, visited);
816 public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
817 return mapHNodeToOutgoingSet;
820 public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
821 return mapHNodeToIncomingSet;
824 public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
825 mapHNodeToOutgoingSet.clear();
826 Set<HNode> keySet = in.keySet();
827 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
828 HNode key = (HNode) iterator.next();
829 Set<HNode> inSet = in.get(key);
830 Set<HNode> newSet = new HashSet<HNode>();
831 newSet.addAll(inSet);
832 mapHNodeToOutgoingSet.put(key, newSet);
836 public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
837 mapHNodeToIncomingSet.clear();
838 Set<HNode> keySet = in.keySet();
839 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
840 HNode key = (HNode) iterator.next();
841 Set<HNode> inSet = in.get(key);
842 Set<HNode> newSet = new HashSet<HNode>();
843 newSet.addAll(inSet);
844 mapHNodeToIncomingSet.put(key, newSet);
848 public void setNodeSet(Set<HNode> inSet) {
850 nodeSet.addAll(inSet);
853 public HierarchyGraph clone() {
854 HierarchyGraph clone = new HierarchyGraph();
855 clone.setDesc(getDesc());
856 clone.setName(getName());
857 clone.setNodeSet(getNodeSet());
858 clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
859 clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
860 clone.setMapDescToHNode(getMapDescToHNode());
861 clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
862 clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
863 clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
864 clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
869 public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
870 return mapMergeNodetoMergingSet;
873 public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
874 this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
877 public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
879 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
880 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
882 return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
885 public void identifyCombinationNodes() {
887 // 1) set combination node flag if a node combines more than one skeleton node.
888 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
889 HNode node = (HNode) iterator.next();
890 if (!node.isSkeleton()) {
891 Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
892 if (reachToSet.size() > 1) {
893 // if (countSkeletonNodes(reachToSet) > 1) {
894 System.out.println("-node=" + node + " reachToSet=" + reachToSet);
895 System.out.println("-set combinationnode=" + node);
896 node.setCombinationNode(true);
897 mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
902 // 2) compute the outgoing set that needs to be directly connected from the combination node
903 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
904 HNode node = (HNode) iterator.next();
905 if (node.isCombinationNode()) {
906 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
907 Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
908 addMapCombineSetToOutgoingSet(combineSet, outSet);
914 public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
915 return mapCombinationNodeToCombineNodeSet;
918 public int countSkeletonNodes(Set<HNode> set) {
921 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
922 HNode node = (HNode) iterator.next();
923 Set<Descriptor> descSet = getDescSetOfNode(node);
924 count += descSet.size();
930 private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
931 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
932 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
934 mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
937 private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
938 // the method returns the set of nodes that are reachable from the current node
939 // and do not combine the same set of skeleton nodes...
941 Set<HNode> visited = new HashSet<HNode>();
942 Set<HNode> reachableSet = new HashSet<HNode>();
943 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
945 recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
950 private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
951 Set<HNode> reachableSet, Set<HNode> visited) {
953 Set<HNode> outSet = getOutgoingNodeSet(node);
954 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
955 HNode outNode = (HNode) iterator.next();
957 if (outNode.isCombinationNode()) {
958 Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
959 if (combineSetOfOutNode.equals(combineSet)) {
960 recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
963 reachableSet.add(outNode);
965 } else if (outNode.isSkeleton()) {
966 reachableSet.add(outNode);
973 private Set<HNode> getReachableNodeSetFrom(HNode node) {
975 Set<HNode> reachableSet = new HashSet<HNode>();
976 Set<HNode> visited = new HashSet<HNode>();
978 recurReachableNodeSetFrom(node, reachableSet, visited);
983 private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
985 Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
986 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
987 HNode outNode = (HNode) iterator.next();
988 reachableSet.add(outNode);
989 if (!visited.contains(outNode)) {
990 visited.add(outNode);
991 recurReachableNodeSetFrom(outNode, reachableSet, visited);
997 public void assignUniqueIndexToNode() {
999 System.out.println("nodeSet=" + nodeSet);
1000 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1001 HNode node = (HNode) iterator.next();
1002 mapHNodeToUniqueIndex.put(node, idx);
1006 BASISTOPELEMENT = new HashSet<Integer>();
1007 for (int i = 1; i < idx + 1; i++) {
1008 BASISTOPELEMENT.add(i);
1012 public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1014 // assign a unique index to a node
1015 assignUniqueIndexToNode();
1017 // compute basis for each node
1018 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1019 HNode node = (HNode) iterator.next();
1021 if (notGenerateSet.contains(node)) {
1022 System.out.println("%%%SKIP =" + node);
1025 Set<Integer> basis = new HashSet<Integer>();
1026 basis.addAll(BASISTOPELEMENT);
1028 Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1029 System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet);
1030 System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1031 // if a node is reachable from the current node
1032 // need to remove the index of the reachable node from the basis
1034 basis.remove(getHNodeIndex(node));
1035 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1036 HNode reachableNode = (HNode) iterator2.next();
1037 System.out.println("reachableNode=" + reachableNode);
1038 System.out.println("getHNodeIndex(reachableNode))="
1039 + mapHNodeToUniqueIndex.get(reachableNode));
1040 int idx = getHNodeIndex(reachableNode);
1044 mapHNodeToBasis.put(node, basis);
1047 // construct the basis set
1049 BasisSet basisSet = new BasisSet();
1051 Set<HNode> keySet = mapHNodeToBasis.keySet();
1052 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1053 HNode node = (HNode) iterator.next();
1054 Set<Integer> basis = mapHNodeToBasis.get(node);
1055 basisSet.addElement(basis, node);
1062 public int getHNodeIndex(HNode node) {
1063 return mapHNodeToUniqueIndex.get(node).intValue();
1066 public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1067 return mapHNodeToUniqueIndex;
1070 public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1071 return mapHNodeToBasis;
1074 public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1076 Set<HNode> combinationNodeSet = new HashSet<HNode>();
1077 Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1078 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1079 HNode key = (HNode) iterator.next();
1081 if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1082 combinationNodeSet.add(key);
1086 return combinationNodeSet;
1089 public void writeGraph() {
1091 String graphName = "hierarchy" + name;
1092 graphName = graphName.replaceAll("[\\W]", "");
1095 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1097 bw.write("digraph " + graphName + " {\n");
1099 Iterator<HNode> iter = nodeSet.iterator();
1101 Set<HNode> addedNodeSet = new HashSet<HNode>();
1103 while (iter.hasNext()) {
1104 HNode u = iter.next();
1106 Set<HNode> outSet = getOutgoingNodeSet(u);
1108 if (outSet.size() == 0) {
1109 if (!addedNodeSet.contains(u)) {
1111 addedNodeSet.add(u);
1114 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1115 HNode v = (HNode) iterator.next();
1116 if (!addedNodeSet.contains(u)) {
1118 addedNodeSet.add(u);
1120 if (!addedNodeSet.contains(v)) {
1122 addedNodeSet.add(v);
1124 bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1133 } catch (IOException e) {
1134 e.printStackTrace();
1138 public boolean contains(HNode node) {
1139 return nodeSet.contains(node);
1142 public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1143 return getOutgoingNodeSet(src).contains(dst);
1146 private String convertMergeSetToString(Set<HNode> mergeSet) {
1148 for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1149 HNode merged = (HNode) iterator.next();
1150 if (merged.isMergeNode()) {
1151 str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1153 str += " " + merged.getName();
1159 private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1161 if (node.isMergeNode()) {
1162 nodeName = node.getNamePropertyString();
1163 Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1164 nodeName += ":" + convertMergeSetToString(mergeSet);
1166 nodeName = node.getNamePropertyString();
1168 bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1171 public int countHopFromTopLocation(HNode node) {
1173 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1175 if (inNodeSet.size() > 0) {
1176 count = recurCountHopFromTopLocation(inNodeSet, 1);
1182 private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1185 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1186 HNode node = (HNode) iterator.next();
1187 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1188 if (inNodeSet.size() > 0) {
1189 int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1190 if (max < recurCount) {