hierarchicalbcengine.java

MacroWeka扩展了著名数据挖掘工具weka

              crossbefore = crossafter;
            nodeLevels = minimizeCrossings(true, nodeLevels);
            crossafter = crossings(nodeLevels);
            i++;
          }
          while(crossafter<crossbefore && i<6);
        }
        //System.out.println("\nCrossings at the end "+
        //                   crossings(nodeLevels)+
        //                   "\n---------------------------------");
        
        m_progress.setValue(10);
        m_progress.setString("Laying out vertices");
        //Laying out graph
        if(m_jRbNaiveLayout.isSelected())
          naiveLayout();
        else
          priorityLayout1();
        m_progress.setValue(11);
        m_progress.setString("Layout Complete");
        m_progress.repaint();
        
        fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
        m_progress.setValue(0);
        m_progress.setString("");
        m_progress.setBorderPainted(false);
      }
    };
    th.start();
  }
  
  /**
   * This method removes the temporary nodes that were
   * added to fill in the gaps, and removes all edges
   * from all nodes in their edges[][] array
   */
  protected void clearTemps_and_EdgesFromNodes() {
    /*
    System.out.println("Before.............");
    for(int i=0; i<m_nodes.size(); i++) {
      GraphNode n = (GraphNode)m_nodes.elementAt(i);
      System.out.println("N: "+n.ID+","+i);
    }
    System.out.println("origNodesSize: "+origNodesSize);
    */
    
    int curSize = m_nodes.size();
    for(int i=origNodesSize; i<curSize; i++)
      m_nodes.removeElementAt(origNodesSize);
    for(int j=0; j<m_nodes.size(); j++)
      ((GraphNode)m_nodes.elementAt(j)).edges = null;
    
    nodeLevels=null;
    
    /*
    System.out.println("After..............");
    for(int i=0; i<m_nodes.size(); i++) {
      GraphNode n = (GraphNode)m_nodes.elementAt(i);
      System.out.println("N: "+n.ID+","+i);
    }
    */
  }
  
  /**
   * This method makes the "graphMatrix" interconnection
   * matrix for the graph given by m_nodes and m_edges
   * vectors. The matix is used by other methods.
   */
  protected void processGraph() {
    origNodesSize = m_nodes.size();
    graphMatrix = new int[m_nodes.size()][m_nodes.size()];
    /*
    System.out.println("The "+m_nodes.size()+" nodes are: ");
    for(int i=0; i<m_nodes.size(); i++)
      System.out.println((String)m_nodes.elementAt(i)+" ");
    System.out.println("\nThe "+m_edges.size()+" edges are: ");
    for(int i=0; i<m_edges.size(); i++)
      System.out.println((GraphEdge)m_edges.elementAt(i));
    */
    for(int i=0; i<m_edges.size(); i++)
      graphMatrix[((GraphEdge)m_edges.elementAt(i)).src]
                 [((GraphEdge)m_edges.elementAt(i)).dest] = 
                                         ((GraphEdge)m_edges.elementAt(i)).type;
    /*
    System.out.print("\t");
    for(int i=0; i<graphMatrix.length; i++)
      System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+" ");
    System.out.println("");
    for(int i=0; i<graphMatrix.length; i++) {
      GraphNode n = (GraphNode)m_nodes.elementAt(i);
      System.out.print(n.ID+"\t");
      for(int j=0; j<graphMatrix[i].length; j++)
        System.out.print(graphMatrix[i][j]+" ");
      System.out.println("");
    }
    */
  }
  
  /*
   * This method makes a proper hierarchy of the graph
   * by first removing cycles, then assigning levels
   * to the nodes and then removing gaps by adding
   * dummy vertices.
   */
  protected void makeProperHierarchy() {
    processGraph();
    
    m_progress.setValue(1);
    m_progress.setString("Removing Cycles");
    //****removing cycles
    removeCycles();
    
    m_progress.setValue(2);
    m_progress.setString("Assigning levels to nodes");
    //****Assigning vertical level to each node
    int nodesLevel[] = new int[m_nodes.size()];
    int depth=0;
    for(int i=0; i<graphMatrix.length; i++) {
      assignLevels(nodesLevel, depth, i, 0);
    }
    
    for(int i=0; i<nodesLevel.length; i++) {
      if(nodesLevel[i]==0) {
        int min=65536;
        for(int j=0; j<graphMatrix[i].length; j++) {
          if(graphMatrix[i][j]==DIRECTED)
            if(min>nodesLevel[j])
              min = nodesLevel[j];
        }
        //if the shallowest child of a parent has a depth greater than 1
        // and it is not a lone parent with no children
        if(min!=65536 && min>1) 
          nodesLevel[i]=min-1;       
      }
    }
    
    //System.out.println("");
    int maxLevel=0;
    for(int i=0; i<nodesLevel.length; i++) {
      if(nodesLevel[i]>maxLevel)
        maxLevel = nodesLevel[i];
      //System.out.println( ((GraphNode)m_nodes.elementAt(i)).ID+" "+i+">"+
      //                    nodesLevel[i]);
    }
    int levelCounts[] = new int[maxLevel+1];
    
    for(int i=0; i<nodesLevel.length; i++) {
      levelCounts[nodesLevel[i]]++;
    }
    //System.out.println("------------------------------------------");
    //****Assigning nodes to each level
    int levelsCounter[] = new int[maxLevel+1];
    nodeLevels = new int[maxLevel+1][];
    for(byte i=0; i<nodesLevel.length; i++) {
      if(nodeLevels[nodesLevel[i]]==null)
        nodeLevels[nodesLevel[i]] = new int[ levelCounts[nodesLevel[i]] ];
      //nodeLevels[nodesLevel[i]].addElement(new Integer(i));
      //System.out.println(((GraphNode)m_nodes.elementAt(i)).ID+" "+
      //                   nodesLevel[i]+">"+levelCounts[nodesLevel[i]]);
      nodeLevels[nodesLevel[i]][levelsCounter[nodesLevel[i]]++] = i;
    }
    
    m_progress.setValue(3);
    m_progress.setString("Removing gaps by adding dummy vertices");
    //*Making a proper Hierarchy by putting in dummy vertices to close all gaps
    if(m_jCbEdgeConcentration.isSelected())
      removeGapsWithEdgeConcentration(nodesLevel);
    else
      removeGaps(nodesLevel);
    
    //After assigning levels and adding dummy vertices
    //System.out.print("\n\t");
    //for(int i=0; i<graphMatrix.length; i++)
    //    System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+" ");
    //System.out.println("");
    //for(int i=0; i<graphMatrix.length; i++) {
    //    System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+"\t");
    //    for(int j=0; j<graphMatrix[i].length; j++)
    //	System.out.print(graphMatrix[i][j]+" ");
    //    System.out.println("");
    //}
    
    //****Updating edges[][] array of nodes from
    //****the interconnection matrix, which will be used
    //****by the Visualizer class to draw edges
    for(int i=0; i<graphMatrix.length; i++) {
      GraphNode n = (GraphNode)m_nodes.elementAt(i);
      int sum=0;
      for(int j=0; j<graphMatrix[i].length; j++)
        if(graphMatrix[i][j]!=0)
          sum++;
      
      n.edges = new int[sum][2];
      for(int j=0, k=0; j<graphMatrix[i].length; j++)
        if(graphMatrix[i][j]!=0) {
          n.edges[k][0] = j;
          n.edges[k][1] = graphMatrix[i][j]; k++;
        }
      //n.edges = graphMatrix[i];
    }
    
    //Interconnection matrices at each level, 1 to n-1
    //printMatrices(nodeLevels);
  }
  
  
  /**
   * This method removes gaps from the graph. It doesn't perform
   * any concentration. It takes as an argument of int[]
   * of length m_nodes.size() containing the level of each
   * node.
   */
  private void removeGaps(int nodesLevel[]) {
    int temp = m_nodes.size();
    int temp2=graphMatrix[0].length, tempCnt=1;
    
    for(int n=0; n<temp; n++) {
      for(int i=0; i<temp2; i++) {
        int len = graphMatrix.length;
        if(graphMatrix[n][i]>0)
          if(nodesLevel[i]>nodesLevel[n]+1) {
            int tempMatrix[][] =
            new int[graphMatrix.length+(nodesLevel[i]-nodesLevel[n]-1)]
                   [graphMatrix.length+(nodesLevel[i]-nodesLevel[n]-1)];
            int level = nodesLevel[n]+1;
            copyMatrix(graphMatrix, tempMatrix);
            
            String s1 = new String("S"+tempCnt++);
            m_nodes.addElement(new GraphNode(s1, s1, SINGULAR_DUMMY)); //true));
            int temp3 [] = new int[nodeLevels[level].length+1];
            //for(int j=0; j<nodeLevels[level].length; j++)
            //    temp3[j] = nodeLevels[level][j];
            System.arraycopy(nodeLevels[level], 0, temp3, 
                             0, nodeLevels[level].length);
            temp3[temp3.length-1] = m_nodes.size()-1;
            nodeLevels[level] = temp3; level++;
            //nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
            //System.out.println("len:"+len+","+nodesLevel[i]+","+
            //                   nodesLevel[n]);
            
            int k;
            for(k=len; k<len+nodesLevel[i]-nodesLevel[n]-1-1; k++) {
              String s2 =  new String("S"+tempCnt);
              m_nodes.addElement( new GraphNode(s2, s2, SINGULAR_DUMMY) ); //true) );
              temp3 = new int[nodeLevels[level].length+1];
              //for(int j=0; j<nodeLevels[level].length; j++)
              //	temp3[j] = nodeLevels[level][j];
              System.arraycopy(nodeLevels[level], 0, temp3, 
                               0, nodeLevels[level].length);
              temp3[temp3.length-1] = m_nodes.size()-1;
              nodeLevels[level++] = temp3;
              //nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
              tempMatrix[k][k+1]=tempMatrix[n][i]; tempCnt++;
              if(k>len)
                tempMatrix[k][k-1]=-1*tempMatrix[n][i];
            }
            
            //temp[lastTempNodeCreated][targetNode]=temp[origNode][targetNode]
            tempMatrix[k][i]=tempMatrix[n][i];
            //System.out.println("k "+((GraphNode)m_nodes.elementAt(k)).ID+
            //		   " i "+((GraphNode)m_nodes.elementAt(i)).ID+
            //		   " n "+((GraphNode)m_nodes.elementAt(n)).ID+
            //		   " len "+((GraphNode)m_nodes.elementAt(len)).ID );
            //temp[origNode][firstTempNodecreated] = temp[origNode][targetNode]
            tempMatrix[n][len] = tempMatrix[n][i]; 
            //temp[firstTempNodeCreated][origNode]  for reverse tracing
            tempMatrix[len][n] = -1*tempMatrix[n][i];
             //temp[targetNode][lastTempNodecreated]  for reverse tracing
            tempMatrix[i][k]   = -1*tempMatrix[n][i]; 
            
            //temp[lastTempNodeCreated][secondlastNode] for reverse tracing
            //but only do this if more than 1 temp nodes are created
            if(k>len)                                  
              tempMatrix[k][k-1] = -1*tempMatrix[n][i];
            
            //temp[origNode][targetNode] = 0 unlinking as they have been
            // linked by a chain of temporary nodes now.
            tempMatrix[n][i]   = 0;                    
            tempMatrix[i][n]   = 0;                    
            
            graphMatrix = tempMatrix;
          }
          else {
            //****Even if there is no gap just add a reference for the
            //****parent to the child for reverse tracing, useful if the
            //****there is a reversed edge from parent to child and therefore
            //****visualizer would know to highlight this edge  when 
            //****highlighting the child.
            graphMatrix[i][n]=-1*graphMatrix[n][i];
          }
      }
    }
    //Interconnection matrices at each level, 1 to n-1 after minimizing edges
    //printMatrices(nodeLevels);
  }
  
  
  /**
   * This method removes gaps from the graph. It tries to minimise the number
   * of edges by concentrating multiple dummy nodes from the same parent and
   * on the same vertical level into one. It takes as an argument of int[]
   * of length m_nodes.size() containing the level of each
   * node.
   */
  private void removeGapsWithEdgeConcentration(int nodesLevel[]) {
    
    final int  temp = m_nodes.size(), temp2=graphMatrix[0].length;
    int tempCnt=1;
    
    for(int n=0; n<temp; n++) {
      for(int i=0; i<temp2; i++) {
        if(graphMatrix[n][i]>0)
          if(nodesLevel[i]>nodesLevel[n]+1) {
            //System.out.println("Processing node "+
            //                   ((GraphNode)m_nodes.elementAt(n)).ID+
            //                   " for "+((GraphNode)m_nodes.elementAt(i)).ID);
            int tempLevel=nodesLevel[n];
            boolean tempNodePresent=false;
            int k=temp;
            int tempnode = n;
            
            while(tempLevel < nodesLevel[i]-1 ) {
              tempNodePresent=false;
              for(; k<graphMatrix.length; k++) {
                if(graphMatrix[tempnode][k]>0) {
                  //System.out.println("tempnode will be true");
                  tempNodePresent = true; break;
                }
              }
              if(tempNodePresent) {
                tempnode=k; k=k+1;
                tempLevel++;
              }
              else {
                if(tempnode!=n)
                  tempnode=k-1;
                //System.out.println("breaking from loop");
                break;
              }
            }
            if(((GraphNode)m_nodes.elementAt(tempnode)).nodeType==SINGULAR_DUMMY)
              ((GraphNode)m_nodes.elementAt(tempnode)).nodeType=PLURAL_DUMMY;