hierarchicalbcengine.java

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

        //if(crossings(tempLevels)<crossings(levels)) { 
        //  System.out.println("Crossings temp: "+crossings(tempLevels)+
        //                     " Crossings levels: "+crossings(levels));
        //      copy2DArray(tempLevels, levels); } //printMatrices(levels); }
        if(crossings(tempLevels)<=crossings(levels))
          copy2DArray(tempLevels, levels);
        //System.out.println("Crossings after PhaseID of phaseIIU, in "+
        //                   "iteration "+i+" of "+(rowBC.length-1)+" at "
        //                   +lindex+", levels: "+crossings(levels)+
        //                   " temp: "+crossings(tempLevels));
        //rowBC = calcRowBC(lindex, levels);
      }
    }
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  protected float [] calcRowBC(final int lindex, final int levels[][]){
    float rowBC[] = new float[levels[lindex].length];
    GraphNode n;
    
    for(int i=0; i<levels[lindex].length; i++) {
      int sum=0;
      n = (GraphNode)m_nodes.elementAt(levels[lindex][i]);
      
      for(int j=0; j<n.edges.length; j++) {
        if(n.edges[j][1]>0) {
          sum++;
          try {
            rowBC[i] = 
              rowBC[i]+indexOfElementInLevel(n.edges[j][0], levels[lindex+1])+1;
          }
          catch(Exception ex) { return null; }
        }
      }
      if(rowBC[i]!=0)
        rowBC[i] = rowBC[i]/sum;
    }
    return rowBC;
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  protected float [] calcColBC(final int lindex, final int levels[][]) {
    float colBC[] = new float[levels[lindex+1].length];
    GraphNode n;
    
    for(int i=0; i<levels[lindex+1].length; i++) {
      int sum=0;
      n = (GraphNode)m_nodes.elementAt(levels[lindex+1][i]);
      
      for(int j=0; j<n.edges.length; j++) {
        if(n.edges[j][1]<1) {
          sum++;
          try{
            colBC[i] =
                colBC[i]+indexOfElementInLevel(n.edges[j][0], levels[lindex])+1;
          }
          catch(Exception ex) { return null; }
        }
      }
      if(colBC[i]!=0)
        colBC[i]=colBC[i]/sum;
    }
    return colBC;
  }
  
  /**
   * Prints out the interconnection matrix at each level.
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  protected void printMatrices(final int levels[][]) {
    int i=0;
    for(i=0; i<levels.length-1; i++) {
      float rowBC[]=null; float colBC[]=null;
      try{
        rowBC = calcRowBC(i, levels); colBC = calcColBC(i, levels);
      }
      catch(NullPointerException ne) {
        System.out.println("i: "+i+" levels.length: "+levels.length);
        ne.printStackTrace();
        return;
      }
      
      System.out.print("\nM"+(i+1)+"\t");
      for(int j=0; j<levels[i+1].length; j++) {
        System.out.print( ((GraphNode)m_nodes.elementAt(levels[i+1][j])).ID +
                          " ");
        //((Integer)levels[i+1].elementAt(j)).intValue())+" ");
      }
      System.out.println("");
      
      for(int j=0; j<levels[i].length; j++) {
        System.out.print( ((GraphNode)m_nodes.elementAt(levels[i][j])).ID+"\t");
        //((Integer)levels[i].elementAt(j)).intValue())+"\t");
        for(int k=0; k<levels[i+1].length; k++) {
          
          System.out.print(graphMatrix[levels[i][j]] 
                                 //((Integer)levels[i].elementAt(j)).intValue()]
                                      [levels[i+1][k]]+" "); 
                         //((Integer)levels[i+1].elementAt(k)).intValue()]+" ");
          
        }
        System.out.println(rowBC[j]);
      }
      System.out.print("\t");
      for(int k=0; k<levels[i+1].length; k++)
        System.out.print(colBC[k]+" ");
    }
    System.out.println("\nAt the end i: "+i+" levels.length: "+levels.length);
  }
  
  /**
   * This methods sorts the vertices in level[] according to their
   * barycenters in BC[], using combsort11. It, however, doesn't touch the
   * vertices with barycenter equal to zero.
   */
    /*
     *  //This method should be removed
     protected static void combSort11(int level[], float BC[]) {  
        int switches, j, top, gap, lhold;
        float hold;
        gap = BC.length;
        do {
            gap=(int)(gap/1.3);
            switch(gap) {
            case 0:
                gap = 1;
                break;
            case 9:
            case 10:
                gap=11;
                break;
            default:
                break;
            }
            switches=0;
            top = BC.length-gap;
            for(int i=0; i<top; i++) {
                j=i+gap;
                if(BC[i]==0 || BC[j]==0)
                    continue;
                if(BC[i] > BC[j]) {
                    hold=BC[i];
                    BC[i]=BC[j];
                    BC[j]=hold;
                    lhold = level[i];
                    level[i] = level[j];
                    level[j] = lhold;
                    switches++;
                }//endif
            }//endfor
        }while(switches>0 || gap>1);
    }
     */
  
  
  /**
   * This methods sorts the vertices in level[] according to their
   * barycenters in BC[], using insertion sort. It, however, doesn't touch the
   * vertices with barycenter equal to zero.
   */
   //Both level and BC have elements in the same order
  protected static void isort(int level[], float BC[]) { 
    float temp;
    int temp2;
    for(int i=0; i<BC.length-1; i++) {
      
      int j=i;
      temp=BC[j+1];
      temp2=level[j+1];
      if(temp==0)
        continue;
      int prej=j+1;
      
      while( j>-1 && (temp<BC[j]|| BC[j]==0) ) {
        if(BC[j]==0){
          j--; continue;}
        else {
          BC[prej] = BC[j];
          level[prej] = level[j];
          prej=j;
          j--;
        }
      }
      //j++;
      BC[prej]    = temp;
      level[prej] = temp2;
      //Integer node = (Integer)level.elementAt(i+1);
      //level.removeElementAt(i+1);
      //level.insertElementAt(node, prej);
    }
  }
  
  
  /**
   * Copies one Matrix of type int[][] to another.
   */
  protected void copyMatrix(int from[][], int to[][]) {
    for(int i=0; i<from.length; i++)
      for(int j=0; j<from[i].length; j++)
        to[i][j]=from[i][j];
  }
  
  /**
   * Copies one array of type int[][] to another.
   */
  protected void copy2DArray(int from[][], int to[][]) {
    for(int i=0; i<from.length; i++) {
      to[i] = new int[from[i].length];
      System.arraycopy(from[i], 0, to[i], 0, from[i].length);
      //for(int j=0; j<from[i].length; j++)
      //	to[i][j] = from[i][j];
    }
  }
  
  /**
   * This method lays out the vertices horizontally, in each level.
   * It simply assings an x value to a vertex according to its
   * index in the level.
   */
  protected void naiveLayout() {
    /*
    if(maxStringWidth==0) {
      int strWidth;
      for(int i=0; i<m_nodes.size(); i++) {
        strWidth = m_fm.stringWidth(((GraphNode)m_nodes.elementAt(i)).lbl);
        if(strWidth>maxStringWidth)
          maxStringWidth=strWidth;
      }
      
      if(m_nodeSize<maxStringWidth)
      {m_nodeSize = maxStringWidth+4; m_nodeArea = m_nodeSize+8; }
    }
    */
    if(nodeLevels==null)
      makeProperHierarchy();
    
    //int nodeHeight = m_nodeHeight*2; //m_fm.getHeight()*2;
    for(int i=0, temp=0; i<nodeLevels.length; i++) {
      for(int j=0; j<nodeLevels[i].length; j++) {
        temp=nodeLevels[i][j];
        //horPositions[temp]=j;
        GraphNode n = (GraphNode)m_nodes.elementAt(temp);
        n.x = j*m_nodeWidth; //horPositions[temp]*m_nodeWidth;
        n.y = i*3*m_nodeHeight;
      }
    }
    //setAppropriateSize();
  }
  
  
  protected int uConnectivity(int lindex, int eindex) {
    int n=0;
    for(int i=0; i<nodeLevels[lindex-1].length; i++)
      if(graphMatrix[ nodeLevels[lindex-1][i] ][ nodeLevels[lindex][eindex] ]>0)
        n++;
    
    return n;
  }
  
  protected int lConnectivity(int lindex, int eindex) {
    int n=0;
    for(int i=0; i<nodeLevels[lindex+1].length; i++)
      if(graphMatrix[ nodeLevels[lindex][eindex] ][ nodeLevels[lindex+1][i] ]>0)
        n++;
    
    return n;
  }
  
  protected int uBCenter(int lindex, int eindex, int horPositions[]) {
    int sum=0;
    
    for(int i=0; i<nodeLevels[lindex-1].length; i++)
      if(graphMatrix[nodeLevels[lindex-1][i]][nodeLevels[lindex][eindex]]>0)
        sum = sum + (horPositions[nodeLevels[lindex-1][i]]);
    if(sum!=0) { // To avoid 0/0
      //System.out.println("uBC Result: "+sum+"/"+
      //                   uConnectivity(lindex,eindex)+
      //                   " = "+(sum/uConnectivity(lindex,eindex)) );
      sum = sum/uConnectivity(lindex,eindex);
    }
    return sum;
  }
  
  
  protected int lBCenter(int lindex, int eindex, int horPositions[]) {
    int sum=0;
    
    for(int i=0; i<nodeLevels[lindex+1].length; i++)
      if(graphMatrix[nodeLevels[lindex][eindex]][nodeLevels[lindex+1][i]]>0)
        sum = sum + (horPositions[nodeLevels[lindex+1][i]]);
    if(sum!=0)  // To avoid 0/0
      sum = sum/lConnectivity(lindex, eindex); //lConectivity;
    return sum;
  }
  
  private void tempMethod(int horPositions[]) {
    
    int minPosition = horPositions[0];
    
    for(int i=0; i<horPositions.length; i++)
      if(horPositions[i]<minPosition)
        minPosition=horPositions[i];
    if(minPosition<0) {
      minPosition = minPosition*-1;
      for(int i=0; i<horPositions.length; i++){
        //System.out.print(horPositions[i]);
        horPositions[i]+=minPosition;
        //System.out.println(">"+horPositions[i]);
      }
    }
    
    //int nodeHeight = m_nodeHeight*2; //m_fm.getHeight()*2;
    for(int i=0, temp=0; i<nodeLevels.length; i++) {
      for(int j=0; j<nodeLevels[i].length; j++) {
        temp=nodeLevels[i][j];
        //horPositions[temp]=j;
        GraphNode n = (GraphNode)m_nodes.elementAt(temp);
        n.x = horPositions[temp]*m_nodeWidth;
        n.y = i*3*m_nodeHeight;
      }
    }
  }
  
  /**
   * This method lays out the vertices horizontally, in each level.
   * See Sugiyama et al. 1981 for full reference.
   */
  protected void priorityLayout1() {
    
    int [] horPositions = new int[m_nodes.size()];
    int maxCount=0;
    
    for(int i=