import IR.Descriptor;
import IR.FieldDescriptor;
+import IR.VarDescriptor;
public class HierarchyGraph {
Descriptor desc;
+ boolean isSCgraph;
+
String name;
- Map<Descriptor, HNode> mapDescToHNode;
- Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
+
+ // graph structure
Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
+
+ Map<Descriptor, HNode> mapDescToHNode;
+ Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
+ Map<HNode, HNode> mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node
+ Map<String, HNode> mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial
+ // node
+ Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
+
+ // data structures for a combination node
Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
+ Map<HNode, Set<HNode>> mapNormalNodeToSCNodeReachToSet;
+
+ Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToFirstNodeOfChainSet;
+
Set<HNode> nodeSet;
- public static int seed = 0;
+ // for the lattice generation
+ Map<HNode, Integer> mapHNodeToUniqueIndex;
+ Map<HNode, Set<Integer>> mapHNodeToBasis;
+ Set<Integer> BASISTOPELEMENT;
public HierarchyGraph() {
mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
nodeSet = new HashSet<HNode>();
+
+ mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
+ mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
+
+ mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
+
+ mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
+
+ mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
+
+ mapNormalNodeToSCNodeReachToSet = new HashMap<HNode, Set<HNode>>();
+
+ mapCombineNodeSetToFirstNodeOfChainSet = new HashMap<Set<HNode>, Set<HNode>>();
+
+ isSCgraph = false;
+ }
+
+ public void setSCGraph(boolean in) {
+ isSCgraph = in;
+ }
+
+ public boolean isSCGraph() {
+ return isSCgraph;
}
public Descriptor getDesc() {
mapHNodeToDescSet.putAll(map);
}
+ public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
+ return mapHNodeToCurrentHNode;
+ }
+
+ public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
+ return mapHNodeNameToCurrentHNode;
+ }
+
+ public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
+ this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
+ }
+
+ public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
+ this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
+ }
+
public Map<Descriptor, HNode> getMapDescToHNode() {
return mapDescToHNode;
}
Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
- System.out.println("src=" + srcHNode + " dstHNode=" + dstHNode + " possibleCycleSet="
- + possibleCycleSet);
-
if (possibleCycleSet.size() > 0) {
- HNode newMergeNode = mergeNodes(possibleCycleSet, false);
+
+ if (possibleCycleSet.size() == 1) {
+ // System.out.println("possibleCycleSet=" + possibleCycleSet + " from src=" + srcHNode
+ // + " dstHNode=" + dstHNode);
+ if (dstHNode.isSharedNode()) {
+ // it has already been assigned shared node.
+ } else {
+ dstHNode.setSharedNode(true);
+ // System.out.println("$$$setShared=" + dstHNode);
+ }
+ return;
+ }
+
+ // System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
+ HNode newMergeNode = mergeNodes(possibleCycleSet);
newMergeNode.setSharedNode(true);
- System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
- System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode);
+
} else {
getIncomingNodeSet(dstHNode).add(srcHNode);
getOutgoingNodeSet(srcHNode).add(dstHNode);
- System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
+ // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
}
}
}
public void addEdge(Descriptor src, Descriptor dst) {
- HNode srcHNode = getHNode(src);
- HNode dstHNode = getHNode(dst);
- addEdge(srcHNode, dstHNode);
+ if (src.equals(LocationInference.LITERALDESC)) {
+ // in this case, we do not need to add a source hnode
+ // just add a destination hnode
+ getHNode(dst);
+ } else {
+ HNode srcHNode = getHNode(src);
+ HNode dstHNode = getHNode(dst);
+ addEdge(srcHNode, dstHNode);
+ }
}
public HNode getHNode(Descriptor d) {
if (!mapDescToHNode.containsKey(d)) {
HNode newNode = new HNode(d);
+
if (d instanceof FieldDescriptor) {
newNode.setSkeleton(true);
}
+
+ if (d.equals(LocationInference.TOPDESC)) {
+ newNode.setSkeleton(true);
+ }
+
+ String symbol = d.getSymbol();
+ if (symbol.startsWith(LocationInference.PCLOC) || symbol.startsWith(LocationInference.RLOC)) {
+ newNode.setSkeleton(true);
+ }
+
mappingDescriptorToHNode(d, newNode);
nodeSet.add(newNode);
}
return mapDescToHNode.get(d);
}
+ public HNode getHNode(String name) {
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ if (node.getName().equals(name)) {
+ return node;
+ }
+ }
+ return null;
+ }
+
private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
mapDescToHNode.put(desc, node);
if (!mapHNodeToDescSet.containsKey(node)) {
skeletonGraph.setMapDescToHNode(getMapDescToHNode());
skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
+ skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
+ skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
+ skeletonGraph.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
return skeletonGraph;
return connected;
}
- private void removeRedundantEdges() {
+ public void removeRedundantEdges() {
for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
HNode src = (HNode) iterator.next();
}
- public void simplifyHierarchyGraph() {
- removeRedundantEdges();
- combineRedundantNodes(false);
- }
-
- public void simplifySkeletonCombinationHierarchyGraph() {
+ public void simplifyHierarchyGraph(LocationInference infer) {
removeRedundantEdges();
- combineRedundantNodes(true);
+ combineRedundantNodes(infer);
}
- private void combineRedundantNodes(boolean onlyCombinationNodes) {
+ public void combineRedundantNodes(LocationInference infer) {
// Combine field/parameter nodes who have the same set of incoming/outgoing edges.
boolean isUpdated = false;
do {
- isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes);
+ isUpdated = combineTwoRedundatnNodes(infer);
} while (isUpdated);
}
- private Set<HNode> getIncomingNodeSet(HNode node) {
+ public Set<HNode> getIncomingNodeSet(HNode node) {
if (!mapHNodeToIncomingSet.containsKey(node)) {
mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
}
return mapHNodeToIncomingSet.get(node);
}
- private Set<HNode> getOutgoingNodeSet(HNode node) {
+ public Set<HNode> getOutgoingNodeSet(HNode node) {
if (!mapHNodeToOutgoingSet.containsKey(node)) {
mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
}
return mapHNodeToOutgoingSet.get(node);
}
- private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes) {
+ private boolean combineTwoRedundatnNodes(LocationInference infer) {
for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
HNode node1 = (HNode) iterator.next();
- if ((onlyCombinationNodes && (!node1.isCombinationNode()))
- || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
+ // if ((onlyCombinationNodes && (!node1.isCombinationNode()))
+ // || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
+ // continue;
+ // }
+
+ if (!node1.isSkeleton()) {
continue;
}
for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
HNode node2 = (HNode) iterator2.next();
- if ((onlyCombinationNodes && (!node2.isCombinationNode()))
- || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
+ // if ((onlyCombinationNodes && (!node2.isCombinationNode()))
+ // || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
+ // continue;
+ // }
+
+ if (!node2.isSkeleton()) {
+ continue;
+ }
+
+ if (!isEligibleForMerging(node1, node2)) {
continue;
}
&& outgoingNodeSet1.equals(outgoingNodeSet2)) {
// need to merge node1 and node2
+ // ///////////////
+ // merge two nodes only if every hierarchy graph in the inheritance hierarchy
+ // that includes both nodes allows the merging of them...
Set<HNode> mergeSet = new HashSet<HNode>();
mergeSet.add(node1);
mergeSet.add(node2);
- mergeNodes(mergeSet, onlyCombinationNodes);
+ infer.isValidMergeInheritanceCheck(desc, mergeSet);
+
+ // ///////////////
+
+ mergeNodes(mergeSet);
return true;
}
return false;
}
+ private boolean isEligibleForMerging(HNode node1, HNode node2) {
+
+ if (node1.isSharedNode() || node2.isSharedNode()) {
+
+ // if either of nodes is a shared node,
+ // all descriptors of node1 & node2 should have a primitive type
+
+ Set<Descriptor> descSet = new HashSet<Descriptor>();
+ descSet.addAll(getDescSetOfNode(node1));
+ descSet.addAll(getDescSetOfNode(node2));
+
+ for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
+ Descriptor desc = (Descriptor) iterator.next();
+ if (!LocationInference.isPrimitive(desc)) {
+ return false;
+ }
+ }
+ return true;
+ }
+ return false;
+ }
+
private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
getIncomingNodeSet(dstHNode).add(srcHNode);
getOutgoingNodeSet(srcHNode).add(dstHNode);
- System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
+ // System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
}
- private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
+ private HNode mergeNodes(Set<HNode> set) {
Set<HNode> incomingNodeSet = new HashSet<HNode>();
Set<HNode> outgoingNodeSet = new HashSet<HNode>();
}
String nodeName;
- if (onlyCombinationNodes) {
- nodeName = "Comb" + (seed++);
- } else {
- nodeName = "Node" + (seed++);
- }
+ boolean isMergeNode = false;
+ nodeName = "MNode" + (LocationInference.locSeed++);
+ isMergeNode = true;
+
HNode newMergeNode = new HNode(nodeName);
+ newMergeNode.setMergeNode(isMergeNode);
nodeSet.add(newMergeNode);
nodeSet.removeAll(set);
// if the input set contains a skeleton node, need to set a new merge node as skeleton also
boolean hasSkeleton = false;
+ boolean hasShared = false;
for (Iterator iterator = set.iterator(); iterator.hasNext();) {
HNode inNode = (HNode) iterator.next();
if (inNode.isSkeleton()) {
hasSkeleton = true;
- break;
+ }
+ if (inNode.isSharedNode()) {
+ hasShared = true;
}
}
+ // System.out.println("-----Set merging node=" + newMergeNode + " as a skeleton=" + set
+ // + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
newMergeNode.setSkeleton(hasSkeleton);
+ newMergeNode.setSharedNode(hasShared);
+
+ // System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
for (Iterator iterator = set.iterator(); iterator.hasNext();) {
HNode node = (HNode) iterator.next();
}
}
- System.out.println("#MERGING NODE=" + set + " new node=" + newMergeNode);
+ Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
+ for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
+ HNode merged = iter.next();
+ if (merged.isSkeleton()) {
+ mergedSkeletonNode.add(merged);
+ }
+ }
+
+ // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
+ // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+ mapMergeNodetoMergingSet.put(newMergeNode, set);
+ for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+ HNode mergedNode = (HNode) iterator.next();
+ addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
+ }
+
+ for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+ HNode hNode = (HNode) iterator.next();
+ // System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
+ }
+
+ // System.out.println();
+
return newMergeNode;
}
- private Set<Descriptor> getDescSetOfNode(HNode node) {
+ private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
+
+ if (curNode.isMergeNode()) {
+ Set<HNode> mergingSet = getMergingSet(curNode);
+ mergingSet.add(curNode);
+ // System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
+ // + mergingSet + " newNode=" + newNode);
+ for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
+ HNode mergingNode = (HNode) iterator.next();
+ mapHNodeToCurrentHNode.put(mergingNode, newNode);
+ mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
+ }
+ } else {
+ mapHNodeToCurrentHNode.put(curNode, newNode);
+ mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
+ }
+
+ }
+
+ public HNode getCurrentHNode(HNode node) {
+ if (!mapHNodeToCurrentHNode.containsKey(node)) {
+ mapHNodeToCurrentHNode.put(node, node);
+ }
+ return mapHNodeToCurrentHNode.get(node);
+ }
+
+ public HNode getCurrentHNode(String nodeName) {
+ return mapHNodeNameToCurrentHNode.get(nodeName);
+ }
+
+ private Set<HNode> getMergingSet(HNode mergeNode) {
+ Set<HNode> mergingSet = new HashSet<HNode>();
+ Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
+ for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ if (node.isMergeNode()) {
+ mergingSet.add(node);
+ mergingSet.addAll(getMergingSet(node));
+ } else {
+ mergingSet.add(node);
+ }
+ }
+ return mergingSet;
+ }
+
+ public Set<Descriptor> getDescSetOfNode(HNode node) {
if (!mapHNodeToDescSet.containsKey(node)) {
mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
}
}
+ public Set<HNode> getReachableSCNodeSet(HNode startNode) {
+ // returns the set of hnodes which is reachable from the startNode and is either SC node or a
+ // node which is directly connected to the SC nodes
+ Set<HNode> reachable = new HashSet<HNode>();
+ Set<HNode> visited = new HashSet<HNode>();
+ visited.add(startNode);
+ recurReachableNodeSet(startNode, visited, reachable);
+ return reachable;
+ }
+
+ public Set<HNode> getSCNodeReachToSet(HNode node) {
+ if (!mapNormalNodeToSCNodeReachToSet.containsKey(node)) {
+ mapNormalNodeToSCNodeReachToSet.put(node, new HashSet<HNode>());
+ }
+ return mapNormalNodeToSCNodeReachToSet.get(node);
+ }
+
+ private void recurReachableNodeSet(HNode node, Set<HNode> visited, Set<HNode> reachable) {
+
+ Set<HNode> outSet = getOutgoingNodeSet(node);
+ for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
+ HNode out = (HNode) iterator.next();
+
+ if (!visited.contains(out)) {
+ visited.add(out);
+ Set<HNode> reachableFromSCNodeSet = reachableFromSCNode(out);
+ mapNormalNodeToSCNodeReachToSet.put(out, reachableFromSCNodeSet);
+ if (out.isSkeleton() || out.isCombinationNode() || reachableFromSCNodeSet.size() > 0) {
+ reachable.add(out);
+ } else {
+ visited.add(out);
+ recurReachableNodeSet(out, visited, reachable);
+ }
+
+ }
+
+ }
+
+ }
+
+ private Set<HNode> reachableFromSCNode(HNode node) {
+ Set<HNode> visited = new HashSet<HNode>();
+ visited.add(node);
+ Set<HNode> reachable = new HashSet<HNode>();
+ recurReachableFromSCNode(node, reachable, visited);
+ return reachable;
+ }
+
+ private void recurReachableFromSCNode(HNode node, Set<HNode> reachable, Set<HNode> visited) {
+ Set<HNode> inNodeSet = getIncomingNodeSet(node);
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ if (inNode.isSkeleton() || inNode.isCombinationNode()) {
+ visited.add(inNode);
+ reachable.add(inNode);
+ } else if (!visited.contains(inNode)) {
+ visited.add(inNode);
+ recurReachableFromSCNode(inNode, reachable, visited);
+ }
+ }
+ }
+
+ public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
+ Set<HNode> combinationNodeSet) {
+ Set<HNode> reachable = new HashSet<HNode>();
+ Set<HNode> visited = new HashSet<HNode>();
+ visited.add(node);
+ recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
+ return reachable;
+ }
+
+ public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
+ Set<HNode> reachable, Set<HNode> combinationNodeSet) {
+
+ Set<HNode> outSet = getOutgoingNodeSet(node);
+ for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
+ HNode out = (HNode) iterator.next();
+
+ if (!visited.contains(out)) {
+ visited.add(out);
+ if (out.isSkeleton()) {
+ reachable.add(out);
+ } else if (out.isCombinationNode()) {
+ if (combinationNodeSet == null) {
+ reachable.add(out);
+ } else if (!combinationNodeSet.contains(out)) {
+ reachable.add(out);
+ } else {
+ recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
+ combinationNodeSet);
+ }
+ } else {
+ recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
+ combinationNodeSet);
+ }
+
+ }
+
+ }
+
+ }
+
+ public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
+ Set<HNode> visited = new HashSet<HNode>();
+ return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
+ }
+
+ public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
+
+ Set<HNode> outSet = getOutgoingNodeSet(node);
+ for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
+ HNode out = (HNode) iterator.next();
+ // if (!visited.contains(out)) {
+ if (out.isCombinationNode() || out.isSkeleton()) {
+ return out;
+ } else {
+ // visited.add(out);
+ return getDirectlyReachableSkeletonCombinationNodeFrom(out);
+ }
+ }
+ // }
+
+ return null;
+ }
+
public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
// if an edge from src to dst introduces a new cycle flow,
// the method returns the set of elements consisting of the cycle
return mapCombinationNodeToCombineNodeSet.get(node);
}
- private HNode getCombinationNode(Set<HNode> combineSet) {
+ public HNode getCombinationNode(Set<HNode> combineSet) {
+ assert isSCGraph();
if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
- String name = "COMB" + (seed++);
+ String name = "COMB" + (LocationInference.locSeed++);
+ System.out.println("-NEW COMB NODE=" + name);
HNode node = new HNode(name);
node.setCombinationNode(true);
nodeSet.add(node);
return mapCombineNodeSetToCombinationNode.get(combineSet);
}
+ public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
+ return mapCombineNodeSetToCombinationNode;
+ }
+
public Set<Set<HNode>> getCombineNodeSet() {
return mapCombineNodeSetToOutgoingNodeSet.keySet();
}
- public void insertCombinationNodesToGraph(HierarchyGraph hierarchyGraph) {
+ public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
// add a new combination node where parameter/field flows are actually combined.
- hierarchyGraph.identifyCombinationNodes();
+ simpleHierarchyGraph.identifyCombinationNodes();
- Set<Set<HNode>> keySet = hierarchyGraph.getCombineNodeSet();
+ Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
Set<HNode> combineSet = (Set<HNode>) iterator.next();
- System.out.println("combineSet=" + combineSet);
+ System.out.println("--combineSet=" + combineSet);
HNode combinationNode = getCombinationNode(combineSet);
+ System.out.println("--combinationNode=" + combinationNode + " combineSet=" + combineSet);
+
+ System.out.println("--hierarchynodes="
+ + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
+
+ Set<HNode> simpleHNodeSet =
+ simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet);
+
+ // check whether a hnode in the simple hierarchy graph is the first node of the chain
+ // if all incoming combination nodes to the hnode have a different combination set from the
+ // hnode, it is the first node of the chain
+ for (Iterator iterator2 = simpleHNodeSet.iterator(); iterator2.hasNext();) {
+ HNode simpleHNode = (HNode) iterator2.next();
+ boolean isFirstNodeOfChain = true;
+ Set<HNode> incomingNodeSet = simpleHierarchyGraph.getIncomingNodeSet(simpleHNode);
+ for (Iterator iterator3 = incomingNodeSet.iterator(); iterator3.hasNext();) {
+ HNode inNode = (HNode) iterator3.next();
+ if (inNode.isCombinationNode()) {
+ Set<HNode> inNodeCombineSet =
+ simpleHierarchyGraph.getCombineSetByCombinationNode(inNode);
+ if (inNodeCombineSet.equals(combineSet)) {
+ isFirstNodeOfChain = false;
+ break;
+ }
+ }
+ }
+ simpleHNode.setDirectCombinationNode(isFirstNodeOfChain);
+ if (isFirstNodeOfChain) {
+ simpleHierarchyGraph.addFirstNodeOfChain(combineSet, simpleHNode);
+ System.out.println("IT IS THE FIRST NODE OF THE CHAIN:" + simpleHNode);
+ }
+ }
// add an edge from a skeleton node to a combination node
for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
HNode inSkeletonNode = (HNode) iterator2.next();
- HNode srcNode = getHNode(inSkeletonNode.getDescriptor());
- System.out.println("inSkeletonNode=" + inSkeletonNode + " srcNode=" + srcNode);
+ // System.out.println("--inSkeletonNode=" + inSkeletonNode + " desc="
+ // + inSkeletonNode.getDescriptor());
+ HNode srcNode;
+ if (inSkeletonNode.getDescriptor() == null) {
+ // the node is merging one...
+ srcNode = inSkeletonNode;
+ } else {
+ srcNode = getHNode(inSkeletonNode.getDescriptor());
+ }
+ // System.out.println("--srcNode=" + srcNode);
addEdgeWithNoCycleCheck(srcNode, combinationNode);
}
// add an edge from the combination node to outgoing nodes
- Set<HNode> outSet = hierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
+ Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
HNode curNode = (HNode) iterator2.next();
if (curNode.isCombinationNode()) {
- Set<HNode> combineNode = hierarchyGraph.getCombineSetByCombinationNode(curNode);
+ Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
HNode outNode = getCombinationNode(combineNode);
addEdgeWithNoCycleCheck(combinationNode, outNode);
} else if (curNode.isSkeleton()) {
- addEdgeWithNoCycleCheck(combinationNode, curNode);
+ // HNode dstNode2 = getHNode(curNode.getDescriptor());
+ HNode dstNode = getCurrentHNode(curNode);
+ // System.out.println("-----curNode=" + curNode + "------->" + dstNode + " dstNode2="
+ // + dstNode2);
+ addEdgeWithNoCycleCheck(combinationNode, dstNode);
}
}
- }
-
- }
-
- private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
- if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
- // need to create a new combination node
- String nodeName = "Comb" + (seed++);
- HNode newCombinationNode = new HNode(nodeName);
- newCombinationNode.setCombinationNode(true);
-
- nodeSet.add(newCombinationNode);
- mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
-
- for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
- HNode reachToNode = (HNode) iterator.next();
- addEdge(reachToNode, newCombinationNode);
- }
+ // System.out.println("--");
}
- HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
- for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
- HNode reachableNode = (HNode) iterator.next();
- addEdge(combinationNode, reachableNode);
- }
-
}
- private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
+ public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
Set<HNode> reachToSet = new HashSet<HNode>();
Set<HNode> visited = new HashSet<HNode>();
-
+ // visited.add(node);
recurSkeletonReachTo(node, reachToSet, visited);
+ // obsolete!
+ // if a node reaches to one of elements in the reachToSet, we do not need to keep it
+ // because the node is not directly connected to the combination node
+ // removeRedundantReachToNodes(reachToSet);
+
return reachToSet;
}
HNode inNode = (HNode) iterator.next();
if (inNode.isSkeleton()) {
+ visited.add(inNode);
reachToSet.add(inNode);
} else if (!visited.contains(inNode)) {
visited.add(inNode);
clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
clone.setMapDescToHNode(getMapDescToHNode());
clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
+ clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
+ clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
+ clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
return clone;
}
+ public void setMapCombineNodeSetToCombinationNode(Map<Set<HNode>, HNode> in) {
+ mapCombineNodeSetToCombinationNode = in;
+ }
+
+ public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
+ return mapMergeNodetoMergingSet;
+ }
+
+ public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
+ this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
+ }
+
public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
HNode node = (HNode) iterator.next();
if (!node.isSkeleton()) {
Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
+ // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
+ // reachToSet = removeTransitivelyReachToSet(reachToSet);
+ Set<HNode> tempSet = reachToSet;
+ // System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet + " tempSet="
+ // + tempSet);
if (reachToSet.size() > 1) {
+ // if (countSkeletonNodes(reachToSet) > 1) {
+ System.out.println("\n-node=" + node + " reachToSet=" + reachToSet);
+ System.out.println("-set combinationnode=" + node);
node.setCombinationNode(true);
mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
+
+ // check if this node is the first node of the chain
+ // boolean isFirstNodeOfChain = false;
+ // Set<HNode> inNodeSet = getIncomingNodeSet(node);
+ // for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
+ // HNode inNode = (HNode) iterator2.next();
+ // if (inNode.isSkeleton()) {
+ // isFirstNodeOfChain = true;
+ // } else if (inNode.isCombinationNode()) {
+ // Set<HNode> inNodeReachToSet = getSkeleteNodeSetReachTo(inNode);
+ // if (!reachToSet.equals(inNodeReachToSet)) {
+ // isFirstNodeOfChain = true;
+ // }
+ // }
+ // }
+ //
+ // if (isFirstNodeOfChain) {
+ // node.setDirectCombinationNode(true);
+ // addFirstNodeOfChain(reachToSet, node);
+ // }
+
}
}
}
}
+ public void addFirstNodeOfChain(Set<HNode> combineSet, HNode firstNode) {
+
+ if (!mapCombineNodeSetToFirstNodeOfChainSet.containsKey(combineSet)) {
+ mapCombineNodeSetToFirstNodeOfChainSet.put(combineSet, new HashSet<HNode>());
+ }
+
+ mapCombineNodeSetToFirstNodeOfChainSet.get(combineSet).add(firstNode);
+
+ }
+
+ public Set<HNode> getFirstNodeOfCombinationNodeChainSet(Set<HNode> combineNodeSet) {
+ return mapCombineNodeSetToFirstNodeOfChainSet.get(combineNodeSet);
+ }
+
+ private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
+
+ Set<HNode> toberemoved = new HashSet<HNode>();
+ Set<HNode> visited = new HashSet<HNode>();
+ for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ visited.add(node);
+ recurIsReachingTo(node, reachToSet, toberemoved, visited);
+ }
+
+ Set<HNode> rSet = new HashSet<HNode>();
+ rSet.addAll(reachToSet);
+ rSet.removeAll(toberemoved);
+ return rSet;
+ }
+
+ private void recurIsReachingTo(HNode curNode, Set<HNode> reachToSet, Set<HNode> toberemoved,
+ Set<HNode> visited) {
+ Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ if (reachToSet.contains(inNode)) {
+ toberemoved.add(inNode);
+ } else if (!visited.contains(inNode)) {
+ visited.add(inNode);
+ recurIsReachingTo(inNode, reachToSet, toberemoved, visited);
+ }
+ }
+
+ }
+
+ public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
+ return mapCombinationNodeToCombineNodeSet;
+ }
+
+ public int countSkeletonNodes(Set<HNode> set) {
+ int count = 0;
+
+ for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ Set<Descriptor> descSet = getDescSetOfNode(node);
+ count += descSet.size();
+ }
+
+ return count;
+ }
+
private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
}
+ private Set<HNode> getReachableNodeSetFrom(HNode node) {
+
+ Set<HNode> reachableSet = new HashSet<HNode>();
+ Set<HNode> visited = new HashSet<HNode>();
+
+ recurReachableNodeSetFrom(node, reachableSet, visited);
+
+ return reachableSet;
+ }
+
+ private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
+
+ Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
+ for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
+ HNode outNode = (HNode) iterator.next();
+ reachableSet.add(outNode);
+ if (!visited.contains(outNode)) {
+ visited.add(outNode);
+ recurReachableNodeSetFrom(outNode, reachableSet, visited);
+ }
+ }
+
+ }
+
+ public void assignUniqueIndexToNode() {
+ int idx = 1;
+ // System.out.println("nodeSet=" + nodeSet);
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ mapHNodeToUniqueIndex.put(node, idx);
+ idx++;
+ }
+
+ BASISTOPELEMENT = new HashSet<Integer>();
+ for (int i = 1; i < idx + 1; i++) {
+ BASISTOPELEMENT.add(i);
+ }
+ }
+
+ public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
+
+ // assign a unique index to a node
+ assignUniqueIndexToNode();
+
+ // compute basis for each node
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+
+ if (notGenerateSet.contains(node)) {
+ System.out.println("%%%SKIP =" + node);
+ continue;
+ }
+ Set<Integer> basis = new HashSet<Integer>();
+ basis.addAll(BASISTOPELEMENT);
+
+ Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
+ // System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet);
+ // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
+ // if a node is reachable from the current node
+ // need to remove the index of the reachable node from the basis
+
+ basis.remove(getHNodeIndex(node));
+ for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
+ HNode reachableNode = (HNode) iterator2.next();
+ // System.out.println("reachableNode=" + reachableNode);
+ // System.out.println("getHNodeIndex(reachableNode))="
+ // + mapHNodeToUniqueIndex.get(reachableNode));
+ int idx = getHNodeIndex(reachableNode);
+ basis.remove(idx);
+ }
+
+ mapHNodeToBasis.put(node, basis);
+ }
+
+ // construct the basis set
+
+ BasisSet basisSet = new BasisSet();
+
+ Set<HNode> keySet = mapHNodeToBasis.keySet();
+ for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ Set<Integer> basis = mapHNodeToBasis.get(node);
+ basisSet.addElement(basis, node);
+ }
+
+ return basisSet;
+
+ }
+
+ public int getHNodeIndex(HNode node) {
+ return mapHNodeToUniqueIndex.get(node).intValue();
+ }
+
+ public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
+ return mapHNodeToUniqueIndex;
+ }
+
+ public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
+ return mapHNodeToBasis;
+ }
+
+ public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
+
+ Set<HNode> combinationNodeSet = new HashSet<HNode>();
+ Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
+ for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+ HNode key = (HNode) iterator.next();
+
+ if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
+ combinationNodeSet.add(key);
+ }
+ }
+
+ return combinationNodeSet;
+ }
+
public void writeGraph() {
+ writeGraph(false);
+ }
+
+ public void writeGraph(boolean isSimple) {
String graphName = "hierarchy" + name;
graphName = graphName.replaceAll("[\\W]", "");
+ if (isSimple) {
+ graphName += "_PAPER";
+ }
+
+ // System.out.println("***graphName=" + graphName + " node siz=" + nodeSet.size());
+
try {
BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
if (outSet.size() == 0) {
if (!addedNodeSet.contains(u)) {
- drawNode(bw, u);
+ if (!isSimple) {
+ drawNode(bw, u);
+ } else {
+ drawNodeName(bw, u);
+ }
addedNodeSet.add(u);
}
} else {
for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
HNode v = (HNode) iterator.next();
if (!addedNodeSet.contains(u)) {
- drawNode(bw, u);
+ if (!isSimple) {
+ drawNode(bw, u);
+ } else {
+ drawNodeName(bw, u);
+ }
addedNodeSet.add(u);
}
if (!addedNodeSet.contains(v)) {
- drawNode(bw, v);
+ if (!isSimple) {
+ drawNode(bw, v);
+ } else {
+ drawNodeName(bw, v);
+ }
addedNodeSet.add(v);
}
bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
}
}
+ public boolean contains(HNode node) {
+ return nodeSet.contains(node);
+ }
+
+ public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
+ return getOutgoingNodeSet(src).contains(dst);
+ }
+
+ private String convertMergeSetToString(Set<HNode> mergeSet) {
+ String str = "";
+ for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
+ HNode merged = (HNode) iterator.next();
+ if (merged.isMergeNode()) {
+ str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
+ } else {
+ str += " " + merged.getName();
+ }
+ }
+ return str;
+ }
+
+ private void drawNodeName(BufferedWriter bw, HNode node) throws IOException {
+ String nodeName = node.getNamePropertyString();
+ bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
+ }
+
private void drawNode(BufferedWriter bw, HNode node) throws IOException {
- String shared = "";
- if (node.isSharedNode()) {
- shared = "*";
+ String nodeName;
+ if (node.isMergeNode()) {
+ nodeName = node.getNamePropertyString();
+ Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
+ // System.out.println("node=" + node + " mergeSet=" + mergeSet);
+ nodeName += ":" + convertMergeSetToString(mergeSet);
+ } else {
+ nodeName = node.getNamePropertyString();
+ }
+ bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
+ }
+
+ public int countHopFromTopLocation(HNode node) {
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(node);
+ int count = 0;
+ if (inNodeSet.size() > 0) {
+ count = recurCountHopFromTopLocation(inNodeSet, 1);
}
- bw.write(node.getName() + " [label=\"" + node.getName() + shared + "\"]" + ";\n");
+
+ return count;
}
+ private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
+
+ int max = curCount;
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ Set<HNode> inNodeSet = getIncomingNodeSet(node);
+ if (inNodeSet.size() > 0) {
+ int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
+ if (max < recurCount) {
+ max = recurCount;
+ }
+ }
+ }
+ return max;
+ }
+
+ public int computeDistance(HNode startNode, Set<HNode> endNodeSet, Set<HNode> combineSet) {
+ System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet);
+ return recur_computeDistance(startNode, startNode, endNodeSet, 0, combineSet);
+ }
+
+ private int recur_computeDistance(HNode startNode, HNode curNode, Set<HNode> endNodeSet,
+ int count, Set<HNode> combineSet) {
+
+ if (!curNode.equals(startNode)) {
+ // do not count the start node
+ count++;
+ }
+
+ if (endNodeSet.contains(curNode)) {
+ // it reaches to one of endNodeSet
+ return count;
+ }
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+
+ int curMaxDistance = 0;
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ // traverse more...
+
+ if (inNode.isCombinationNode() && combineSet != null) {
+ // check if inNode have the same combination set of the starting node
+ Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
+ if (!inNodeCombineSet.equals(combineSet)) {
+ continue;
+ }
+ }
+
+ System.out.println(" traverse more to" + inNode + " before-count=" + count);
+ int dist = recur_computeDistance(startNode, inNode, endNodeSet, count, combineSet);
+ if (dist > curMaxDistance) {
+ curMaxDistance = dist;
+ }
+ }
+ return curMaxDistance;
+ }
+
+ public int computeDistance2(HNode startNode, Set<HNode> endNodeSet, Set<HNode> combineSet) {
+ System.out.println("#####computeDistance startNode=" + startNode + " endNode=" + endNodeSet);
+ return recur_computeDistance2(startNode, startNode, endNodeSet, 0, 0, combineSet);
+ }
+
+ private int recur_computeDistance2(HNode startNode, HNode curNode, Set<HNode> endNodeSet,
+ int sharedCount, int nonSharedCount, Set<HNode> combineSet) {
+
+ if (!curNode.equals(startNode)) {
+ // do not count the start node
+ if (curNode.isSharedNode()) {
+ sharedCount++;
+ } else {
+ nonSharedCount++;
+ }
+ }
+
+ if (endNodeSet.contains(curNode)) {
+ // it reaches to one of endNodeSet
+ if (sharedCount > nonSharedCount) {
+ return sharedCount;
+ } else {
+ return nonSharedCount;
+ }
+ }
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+
+ int curMaxDistance = 0;
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ // traverse more...
+
+ if (inNode.isCombinationNode() && combineSet != null) {
+ // check if inNode have the same combination set of the starting node
+ Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
+ if (!inNodeCombineSet.equals(combineSet)) {
+ continue;
+ }
+ }
+
+ System.out.println(" traverse more to" + inNode + " sC=" + sharedCount + " nC="
+ + nonSharedCount);
+ int dist =
+ recur_computeDistance2(startNode, inNode, endNodeSet, sharedCount, nonSharedCount,
+ combineSet);
+ if (dist > curMaxDistance) {
+ curMaxDistance = dist;
+ }
+ }
+ return curMaxDistance;
+ }
+
+ public int countNonSharedNode(HNode startNode, Set<HNode> endNodeSet) {
+ System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
+ return recur_countNonSharedNode(startNode, endNodeSet, 0);
+ }
+
+ private int recur_countNonSharedNode(HNode startNode, Set<HNode> endNodeSet, int count) {
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
+
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ if (endNodeSet.contains(inNode)) {
+ count++;
+ return count;
+ } else {
+ if (!inNode.isSharedNode()) {
+ count++;
+ }
+ return recur_countNonSharedNode2(inNode, endNodeSet, count);
+ }
+ }
+
+ return 0;
+ }
+
+ public int countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet) {
+ System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
+ return recur_countNonSharedNode2(startNode, endNodeSet, 0);
+ }
+
+ private int recur_countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet, int count) {
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
+
+ if (inNodeSet.size() == 0) {
+ // it is directly connected to the TOP node
+ }
+
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ if (endNodeSet.contains(inNode)) {
+ return count;
+ } else {
+ if (!inNode.isSharedNode()) {
+ count++;
+ }
+ return recur_countNonSharedNode2(inNode, endNodeSet, count);
+ }
+ }
+
+ // System.out.println("startNode=" + startNode + " inNodeSet=" + inNodeSet);
+ // HNode inNode = inNodeSet.iterator().next();
+ return -1;
+ }
}
projects / IRC.git / blobdiff