X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FHierarchyGraph.java;h=d7900939e6d4d6e4f221838c2113f8177527ce35;hb=47cc527f574f19b71e92fceac668fb8c0655b13b;hp=ce62cf5707ae216f044a12cc33ba53c5017dd2e1;hpb=9e20e6312d78b49358821f39e34967cabb4a51c3;p=IRC.git

diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java
index ce62cf57..d7900939 100644
--- a/Robust/src/Analysis/SSJava/HierarchyGraph.java
+++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java
@@ -8,15 +8,17 @@ import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
+import java.util.Stack;
 
 import IR.Descriptor;
 import IR.FieldDescriptor;
-import IR.VarDescriptor;
 
 public class HierarchyGraph {
 
   Descriptor desc;
 
+  boolean isSCgraph;
+
   String name;
 
   // graph structure
@@ -38,6 +40,8 @@ public class HierarchyGraph {
 
   Map<HNode, Set<HNode>> mapNormalNodeToSCNodeReachToSet;
 
+  Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToFirstNodeOfChainSet;
+
   Set<HNode> nodeSet;
 
   // for the lattice generation
@@ -66,6 +70,18 @@ public class HierarchyGraph {
     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() {
@@ -141,19 +157,19 @@ public class HierarchyGraph {
     if (possibleCycleSet.size() > 0) {
 
       if (possibleCycleSet.size() == 1) {
-        System.out.println("possibleCycleSet=" + possibleCycleSet + "  from src=" + srcHNode
-            + " dstHNode=" + dstHNode);
+        // 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);
+          // System.out.println("$$$setShared=" + dstHNode);
         }
         return;
       }
 
-      System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
-      HNode newMergeNode = mergeNodes(possibleCycleSet, false);
+      // System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
+      HNode newMergeNode = mergeNodes(possibleCycleSet);
       newMergeNode.setSharedNode(true);
 
     } else {
@@ -298,21 +314,16 @@ public class HierarchyGraph {
 
   }
 
-  public void simplifyHierarchyGraph() {
-    removeRedundantEdges();
-    combineRedundantNodes(false);
-  }
-
-  public void simplifySkeletonCombinationHierarchyGraph() {
+  public void simplifyHierarchyGraph(LocationInference infer) {
     removeRedundantEdges();
-    combineRedundantNodes(true);
+    combineRedundantNodes(infer);
   }
 
-  public 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);
   }
 
@@ -330,12 +341,16 @@ public class HierarchyGraph {
     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;
       }
 
@@ -345,11 +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;
         }
 
+        // System.out.println("node1=" + node1 + " vs node2=" + node2);
         if (!isEligibleForMerging(node1, node2)) {
           continue;
         }
@@ -359,14 +379,26 @@ public class HierarchyGraph {
           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
           Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
 
+          // System.out.println(node1 + " " + node2 + " MERGING incoming?=" + incomingNodeSet1
+          // + " vs " + incomingNodeSet2);
+          // System.out.println(node1 + " " + node2 + " MERGING outgoing?=" + outgoingNodeSet1
+          // + " vs " + outgoingNodeSet2);
+
           if (incomingNodeSet1.equals(incomingNodeSet2)
               && outgoingNodeSet1.equals(outgoingNodeSet2)) {
             // need to merge node1 and node2
-
+            // System.out.println("MERGE!!!!!!!!!!!!!");
+            // ///////////////
+            // 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;
           }
 
@@ -396,7 +428,7 @@ public class HierarchyGraph {
       }
       return true;
     }
-    return false;
+    return true;
   }
 
   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
@@ -405,7 +437,7 @@ public class HierarchyGraph {
     // 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>();
@@ -418,12 +450,9 @@ public class HierarchyGraph {
 
     String nodeName;
     boolean isMergeNode = false;
-    if (onlyCombinationNodes) {
-      nodeName = "Comb" + (LocationInference.locSeed++);
-    } else {
-      nodeName = "Node" + (LocationInference.locSeed++);
-      isMergeNode = true;
-    }
+    nodeName = "MNode" + (LocationInference.locSeed++);
+    isMergeNode = true;
+
     HNode newMergeNode = new HNode(nodeName);
     newMergeNode.setMergeNode(isMergeNode);
 
@@ -447,7 +476,7 @@ public class HierarchyGraph {
     newMergeNode.setSkeleton(hasSkeleton);
     newMergeNode.setSharedNode(hasShared);
 
-    System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
+    // System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
 
     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
       HNode node = (HNode) iterator.next();
@@ -494,10 +523,10 @@ public class HierarchyGraph {
 
     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
       HNode hNode = (HNode) iterator.next();
-      System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
+      // System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
     }
 
-    System.out.println();
+    // System.out.println();
 
     return newMergeNode;
   }
@@ -507,8 +536,8 @@ public class HierarchyGraph {
     if (curNode.isMergeNode()) {
       Set<HNode> mergingSet = getMergingSet(curNode);
       mergingSet.add(curNode);
-      System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
-          + mergingSet + " newNode=" + newNode);
+      // 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);
@@ -752,8 +781,10 @@ public class HierarchyGraph {
   }
 
   public HNode getCombinationNode(Set<HNode> combineSet) {
+    assert isSCGraph();
     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
       String name = "COMB" + (LocationInference.locSeed++);
+      System.out.println("-NEW COMB NODE=" + name);
       HNode node = new HNode(name);
       node.setCombinationNode(true);
       nodeSet.add(node);
@@ -780,9 +811,48 @@ public class HierarchyGraph {
     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);
       HNode combinationNode = getCombinationNode(combineSet);
-      System.out.println("--combinationNode=" + combinationNode + "   combineSet=" + combineSet);
+      System.out.println("\n@INSERT COMBINATION NODE FOR combineSet=" + combineSet
+          + "  --combinationNode=" + combinationNode);
+      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);
+          // System.out.println("--->INCOMING NODES=");
+          // Set<HNode> inNodeSet = simpleHierarchyGraph.getIncomingNodeSet(simpleHNode);
+          // for (Iterator iterator3 = inNodeSet.iterator(); iterator3.hasNext();) {
+          // HNode inNode = (HNode) iterator3.next();
+          // System.out.println("          inNode=" + inNode + "   combineSet="
+          // + simpleHierarchyGraph.getCombineSetByCombinationNode(inNode) + " SKELETON TO SET="
+          // + simpleHierarchyGraph.getSkeleteNodeSetReachTo(inNode));
+          // }
+        }
+      }
+
       // add an edge from a skeleton node to a combination node
       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
         HNode inSkeletonNode = (HNode) iterator2.next();
@@ -796,6 +866,7 @@ public class HierarchyGraph {
           srcNode = getHNode(inSkeletonNode.getDescriptor());
         }
         // System.out.println("--srcNode=" + srcNode);
+        System.out.println("     ADD EDGE SRC=" + srcNode + " -> " + combinationNode);
         addEdgeWithNoCycleCheck(srcNode, combinationNode);
       }
 
@@ -816,38 +887,29 @@ public class HierarchyGraph {
         }
       }
 
-      System.out.println("--");
+      // System.out.println("--");
 
     }
 
   }
 
-  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" + (LocationInference.locSeed++);
-      HNode newCombinationNode = new HNode(nodeName);
-      newCombinationNode.setCombinationNode(true);
-
-      nodeSet.add(newCombinationNode);
-      mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
+  public Set<HNode> getSkeleteNodeSetReachToNoTransitive(HNode node) {
 
-      for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
-        HNode reachToNode = (HNode) iterator.next();
-        addEdge(reachToNode, newCombinationNode);
-      }
-
-    }
+    Set<HNode> reachToSet = new HashSet<HNode>();
+    Set<HNode> visited = new HashSet<HNode>();
+    // visited.add(node);
+    recurSkeletonReachTo(node, reachToSet, visited);
 
-    HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
-    for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
-      HNode reachableNode = (HNode) iterator.next();
-      addEdge(combinationNode, reachableNode);
-    }
+    // 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 removeTransitivelyReachToSet(reachToSet);
+    // return reachToSet;
   }
 
-  private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
+  public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 
     Set<HNode> reachToSet = new HashSet<HNode>();
     Set<HNode> visited = new HashSet<HNode>();
@@ -859,24 +921,9 @@ public class HierarchyGraph {
     // because the node is not directly connected to the combination node
     // removeRedundantReachToNodes(reachToSet);
 
-    return reachToSet;
-  }
-
-  private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
-
-    Set<HNode> toberemoved = new HashSet<HNode>();
-    for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
-      HNode cur = (HNode) iterator.next();
-
-      for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
-        HNode dst = (HNode) iterator2.next();
-        if (!cur.equals(dst) && reachTo(cur, dst)) {
-          // it is redundant
-          toberemoved.add(cur);
-        }
-      }
-    }
-    reachToSet.removeAll(toberemoved);
+    // TODO
+    return removeTransitivelyReachToSet(reachToSet);
+    // return reachToSet;
   }
 
   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
@@ -949,6 +996,10 @@ public class HierarchyGraph {
     return clone;
   }
 
+  public void setMapCombineNodeSetToCombinationNode(Map<Set<HNode>, HNode> in) {
+    mapCombineNodeSetToCombinationNode = in;
+  }
+
   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
     return mapMergeNodetoMergingSet;
   }
@@ -972,13 +1023,48 @@ public class HierarchyGraph {
       HNode node = (HNode) iterator.next();
       if (!node.isSkeleton()) {
         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
-        System.out.println("$node=" + node + "   reachToNodeSet=" + reachToSet);
+        // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
+        // System.out.println("ALL REACH SET=" + reachToSet);
+        // reachToSet = removeTransitivelyReachToSet(reachToSet);
+
+        Set<HNode> curReachToSet = new HashSet<HNode>();
+        for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
+          HNode reachSkeletonNode = (HNode) iterator2.next();
+          curReachToSet.add(getCurrentHNode(reachSkeletonNode));
+        }
+
+        // System.out.println("-curReachToSett=" + curReachToSet + "  reachToSet=" + reachToSet);
+
+        reachToSet = curReachToSet;
+        // System.out.println("$node=" + node + "   reachToNodeSet=" + reachToSet + " tempSet="
+        // + tempSet);
         if (reachToSet.size() > 1) {
           // if (countSkeletonNodes(reachToSet) > 1) {
-          System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
+          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);
+          // }
+
         }
       }
     }
@@ -995,6 +1081,52 @@ 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;
   }
@@ -1183,6 +1315,8 @@ public class HierarchyGraph {
       graphName += "_PAPER";
     }
 
+    // System.out.println("***graphName=" + graphName + "   node siz=" + nodeSet.size());
+
     try {
       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 
@@ -1270,6 +1404,7 @@ public class HierarchyGraph {
     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();
@@ -1304,4 +1439,205 @@ public class HierarchyGraph {
     return max;
   }
 
+  public Stack<String> computeDistance2(HNode startNode, Set<HNode> endNodeSet,
+      HierarchyGraph scGraph, Set<HNode> combineSet) {
+    System.out
+        .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
+    Stack<String> trace = new Stack<String>();
+    return recur_computeDistance2(startNode, endNodeSet, scGraph, 0, combineSet, trace);
+  }
+
+  public Stack<String> computeDistance(HNode startNode, Set<HNode> endNodeSet,
+      HierarchyGraph scGraph, Set<HNode> combineSet) {
+    System.out
+        .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
+    Stack<String> trace = new Stack<String>();
+    return recur_computeDistance(startNode, endNodeSet, 0, combineSet, trace);
+  }
+
+  private Stack<String> recur_computeDistance(HNode curNode, Set<HNode> endNodeSet, int count,
+      Set<HNode> combineSet, Stack<String> trace) {
+
+    if (!curNode.isSkeleton()) {
+      if (curNode.isSharedNode()) {
+        trace.add("S");
+      } else {
+        trace.add("N");
+      }
+    }
+
+    if (endNodeSet.contains(curNode)) {
+      // it reaches to one of endNodeSet
+      return trace;
+    }
+
+    Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+
+    int curMaxDistance = 0;
+    Stack<String> curMaxTrace = (Stack<String>) trace.clone();
+    ;
+    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-trace=" + trace);
+      Stack<String> newTrace = (Stack<String>) trace.clone();
+      Stack<String> curTrace =
+          recur_computeDistance(inNode, endNodeSet, count, combineSet, newTrace);
+      // System.out.println("curTracerTrace=" + curTrace);
+
+      if (curTrace != null && curTrace.size() > curMaxDistance) {
+        curMaxTrace = curTrace;
+        curMaxDistance = curTrace.size();
+      }
+    }
+    return curMaxTrace;
+
+  }
+
+  private Stack<String> recur_computeDistance2(HNode curNode, Set<HNode> endNodeSet,
+      HierarchyGraph scGraph, int count, Set<HNode> combineSet, Stack<String> trace) {
+
+    if (!curNode.isSkeleton()) {
+      if (curNode.isSharedNode()) {
+        trace.add("S");
+      } else {
+        trace.add("N");
+      }
+    }
+
+    System.out.println("   curNode=" + curNode + "  curTrace=" + trace);
+    // System.out.println("     curNode=" + curNode + "  curSCNode="
+    // + scGraph.getCurrentHNode(curNode) + " contains="
+    // + endNodeSet.contains(scGraph.getCurrentHNode(curNode)));
+    if (endNodeSet.contains(scGraph.getCurrentHNode(curNode))) {
+      // it reaches to one of endNodeSet
+      return trace;
+    }
+
+    Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+
+    int curMaxDistance = 0;
+    Stack<String> curMaxTrace = (Stack<String>) trace.clone();
+    ;
+    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;
+        }
+      }
+
+      // Stack<String> newTrace = (Stack<String>) trace.clone();
+      // Stack<String> curTrace =
+      // recur_computeDistance(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
+      // if (curTrace != null) {
+      // return curTrace;
+      // }
+
+      Set<HNode> inReachToNodeSet = getSkeleteNodeSetReachToNoTransitive(inNode);
+      Set<HNode> inCurReachToNodeSet = new HashSet<HNode>();
+      for (Iterator iterator2 = inReachToNodeSet.iterator(); iterator2.hasNext();) {
+        HNode aboveNode = (HNode) iterator2.next();
+        inCurReachToNodeSet.add(getCurrentHNode(aboveNode));
+      }
+
+      if (combineSet != null || inCurReachToNodeSet.equals(endNodeSet)) {
+        System.out
+            .println("        traverse to incomingNode=" + inNode + "  before-trace=" + trace);
+
+        Stack<String> newTrace = (Stack<String>) trace.clone();
+        Stack<String> curTrace =
+            recur_computeDistance2(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
+
+        if (curTrace != null && curTrace.size() > curMaxDistance) {
+          curMaxTrace = curTrace;
+          curMaxDistance = curTrace.size();
+        }
+      } else {
+        System.out.println("NOT TRAVERSE a new inNode=" + inNode + " inReachToNodeSet="
+            + inCurReachToNodeSet);
+      }
+
+    }
+    return curMaxTrace;
+  }
+
+  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;
+  }
+
+  public void removeIsolatedNodes() {
+    Set<HNode> toberemoved = new HashSet<HNode>();
+    for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+      HNode node = (HNode) iterator.next();
+      if (getIncomingNodeSet(node).isEmpty() && getOutgoingNodeSet(node).isEmpty()) {
+        toberemoved.add(node);
+      }
+    }
+    nodeSet.removeAll(toberemoved);
+  }
 }