changes.
[IRC.git] / Robust / src / Analysis / SSJava / HierarchyGraph.java
index 02625d92ed469c44987e28f3292834835985a1de..c14864e74ff82693cc5d7cd61b38ae7f030ef391 100644 (file)
@@ -11,24 +11,43 @@ import java.util.Set;
 
 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>>();
@@ -40,6 +59,29 @@ public class HierarchyGraph {
     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() {
@@ -72,6 +114,22 @@ public class HierarchyGraph {
     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;
   }
@@ -96,18 +154,28 @@ public class HierarchyGraph {
 
     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);
     }
 
   }
@@ -117,10 +185,16 @@ public class HierarchyGraph {
   }
 
   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);
+    }
 
   }
 
@@ -131,15 +205,36 @@ public class HierarchyGraph {
   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)) {
@@ -171,6 +266,9 @@ public class HierarchyGraph {
 
     skeletonGraph.setMapDescToHNode(getMapDescToHNode());
     skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
+    skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
+    skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
+    skeletonGraph.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
 
     return skeletonGraph;
 
@@ -185,7 +283,7 @@ public class HierarchyGraph {
     return connected;
   }
 
-  private void removeRedundantEdges() {
+  public void removeRedundantEdges() {
 
     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
       HNode src = (HNode) iterator.next();
@@ -216,44 +314,43 @@ public class HierarchyGraph {
 
   }
 
-  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;
       }
 
@@ -263,8 +360,16 @@ public class HierarchyGraph {
       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;
         }
 
@@ -277,10 +382,17 @@ public class HierarchyGraph {
               && 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;
           }
 
@@ -291,13 +403,35 @@ public class HierarchyGraph {
     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>();
@@ -309,26 +443,34 @@ public class HierarchyGraph {
     }
 
     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();
@@ -357,11 +499,78 @@ public class HierarchyGraph {
       }
     }
 
-    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>());
     }
@@ -401,6 +610,131 @@ public class HierarchyGraph {
 
   }
 
+  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
@@ -440,9 +774,11 @@ public class HierarchyGraph {
     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);
@@ -453,78 +789,108 @@ public class HierarchyGraph {
     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;
   }
 
@@ -535,6 +901,7 @@ public class HierarchyGraph {
       HNode inNode = (HNode) iterator.next();
 
       if (inNode.isSkeleton()) {
+        visited.add(inNode);
         reachToSet.add(inNode);
       } else if (!visited.contains(inNode)) {
         visited.add(inNode);
@@ -590,10 +957,25 @@ public class HierarchyGraph {
     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)) {
@@ -609,9 +991,38 @@ public class HierarchyGraph {
       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);
+          // }
+
         }
       }
     }
@@ -628,6 +1039,68 @@ public class HierarchyGraph {
 
   }
 
+  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>());
@@ -671,11 +1144,137 @@ public class HierarchyGraph {
 
   }
 
+  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"));
 
@@ -692,18 +1291,30 @@ public class HierarchyGraph {
 
         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");
@@ -720,12 +1331,219 @@ public class HierarchyGraph {
     }
   }
 
+  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;
+  }
 }