hierarchicalbcengine.java

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

          else if(graphMatrix[i][nindex]==DIRECTED) {
            //System.out.println("\nFound double "+nindex+','+i);
            graphMatrix[i][nindex]=DOUBLE;
            graphMatrix[nindex][i]=-DOUBLE;
          }
          else {
            //System.out.println("\nReversing "+nindex+','+i);
            graphMatrix[i][nindex]=REVERSED;
            graphMatrix[nindex][i]=-REVERSED;
          }
        }
    }
  }
  
  /**
   * This method assigns a vertical level to each node.
   * See makeProperHierarchy() to see how to use it.
   */
  protected void assignLevels(int levels[], int depth, int i, int j) {
    //System.out.println(i+","+j);
    if(i>=graphMatrix.length)
      return;
    else if(j>=graphMatrix[i].length)
      return;
    if(graphMatrix[i][j]<=0)
      assignLevels(levels, depth, i, ++j);
    else if(graphMatrix[i][j]==DIRECTED || graphMatrix[i][j]==DOUBLE) {
      if(depth+1>levels[j]) {
        levels[j]=depth+1;
        assignLevels(levels, depth+1, j, 0);
      }
      assignLevels(levels, depth, i, ++j);
    }
  }
  
  
  /**
   * This method minimizes the number of edge crossings using the BaryCenter
   * heuristics given by Sugiyama et al. 1981
   * This method processes the graph topdown if reversed is false,
   * otherwise it does bottomup.
   */
  private int[][] minimizeCrossings(boolean reversed, int nodeLevels[][]) {
    
    //Minimizing crossings using Sugiyama's method
    if(reversed==false) {
      for(int times=0; times<1; times++) {
        int tempLevels[][] = new int[nodeLevels.length][];
        
        //System.out.println("---------------------------------");
        //System.out.println("Crossings before PHaseID: "+
        //                   crossings(nodeLevels));
        copy2DArray(nodeLevels, tempLevels);
        for(int i=0; i<nodeLevels.length-1; i++)   //Down
          phaseID(i, tempLevels);
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        
        //System.out.println("\nCrossings before PHaseIU: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=nodeLevels.length-2; i>=0; i--)  //Up
          phaseIU(i, tempLevels);
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        
        //System.out.println("\nCrossings before PHaseIID: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=0; i<nodeLevels.length-1; i++) {   //Down
          phaseIID(i, tempLevels);
        }
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        //System.out.println("Crossings temp:"+crossings(tempLevels)+
        //                   " graph:"+crossings(nodeLevels));
        //printMatrices(nodeLevels);
        
        //System.out.println("\nCrossings before PHaseIIU: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=nodeLevels.length-2; i>=0; i--) {   //Up
          phaseIIU(i, tempLevels);
        }
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        ///System.out.println("Crossings temp:"+crossings(tempLevels)+
        //                    " graph:"+crossings(nodeLevels));
        ///printMatrices(nodeLevels);
        //System.out.println("\nCrossings after phaseIIU: "+
        //                   crossings(nodeLevels));
      }
      return nodeLevels;
    }
    else {
      for(int times=0; times<1; times++) {
        int tempLevels[][] = new int[nodeLevels.length][];
        
        //System.out.println("---------------------------------");
        //System.out.println("\nCrossings before PHaseIU: "+
        //                   crossings(nodeLevels));
        copy2DArray(nodeLevels, tempLevels);
        for(int i=nodeLevels.length-2; i>=0; i--)  //Up
          phaseIU(i, tempLevels);
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        //printMatrices(nodeLevels);
        
        //System.out.println("Crossings before PHaseID: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=0; i<nodeLevels.length-1; i++)   //Down
          phaseID(i, tempLevels);
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        ///printMatrices(nodeLevels);
        
        //System.out.println("\nCrossings before PHaseIIU: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=nodeLevels.length-2; i>=0; i--) {   //Up
          phaseIIU(i, tempLevels);
        }
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        //printMatrices(nodeLevels);
        
        //System.out.println("\nCrossings before PHaseIID: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=0; i<nodeLevels.length-1; i++) {   //Down
          phaseIID(i, tempLevels);
        }
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        ///printMatrices(nodeLevels);
        //System.out.println("\nCrossings after phaseIID: "+
        //                   crossings(nodeLevels));
      }
      return nodeLevels;
    }
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   * lindex is the index of the level we want to process.
   * In this method we'll sort the vertices at the level one
   * below lindex according to their UP-barycenters (or column
   * barycenters).
   */
  protected void phaseID(final int lindex, final int levels[][]) {
    float colBC[]; //= new float[levels[lindex+1].size()];
    colBC = calcColBC(lindex, levels);
    
    //System.out.println("In ID Level"+(lindex+1)+":");
    //System.out.print("\t");
    //for(int i=0; i<colBC.length; i++)
    //   {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    //    }
    //System.out.println("");
    //colBC = calcColBC1(lindex, levels);
    //for(int i=0; i<colBC.length; i++)
    //  {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    //    }
    //System.out.println("");
    //System.out.print("\n\tNodes ");
    //for(int i=0; i<levels[lindex+1].length; i++)
    //    System.out.print(levels[lindex+1][i]+" ");
    //System.out.println("");
    //System.out.println("\nCrossings: "+crossings(levels));
    //inspect(false, lindex, levels, colBC);
    
    isort(levels[lindex+1], colBC);
    //combSort11(levels[lindex+1], colBC);
    //System.out.println("After sorting");
    //System.out.print("\t");
    //for(int i=0; i<colBC.length; i++)
    //    {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    //    }
    //System.out.print("\n\tNodes ");
    //for(int i=0; i<levels[lindex+1].length; i++)
    //    System.out.print(levels[lindex+1][i]+" ");
    //System.out.println("\nCrossings: "+crossings(levels));
    ///System.out.println("");
  }
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   * lindex is the index of the level we want to process.
   * In this method we'll sort the vertices at the level
   * lindex according to their DOWN-barycenters (or row
   * barycenters).
   */
  public void phaseIU(final int lindex, final int levels[][]) {
    float rowBC[];
    rowBC = calcRowBC(lindex, levels);
    
    //System.out.println("In IU Level"+(lindex+1)+":");
    //System.out.print("\t");
    //for(int i=0; i<rowBC.length; i++)
    //    {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    //    }
    //    System.out.print("\n\t");
    //    rowBC = calcRowBC1(lindex, levels);
    //    for(int i=0; i<rowBC.length; i++)
    //      {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    //      }
    //    System.out.println("");
    //System.out.print("\n\tNodes ");
    //for(int i=0; i<levels[lindex].length; i++)
    //    System.out.print(levels[lindex][i]+" ");
    //System.out.println("\nCrossings: "+crossings(levels));
    //inspect(true, lindex, levels, rowBC);
    
    isort(levels[lindex], rowBC);
    //combSort11(levels[lindex], rowBC);
    //System.out.println("After sorting\n\t");
    //for(int i=0; i<rowBC.length; i++)
    //    {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    //    }
    //System.out.print("\n\tNodes ");
    //for(int i=0; i<levels[lindex].length; i++)
    //    System.out.print(levels[lindex][i]+" ");
    //System.out.println("\nCrossings: "+crossings(levels));
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  public void phaseIID(final int lindex, final int levels[][]) {
    float colBC[];
    colBC = calcColBC(lindex, levels);
    
    //System.out.println("getting into phase IID");
    for(int i=0; i<colBC.length-1; i++) {
      if(colBC[i]==colBC[i+1]) {
        //System.out.println("Crossings before begining of iteration: "+
        //                   crossings(levels));
        int tempLevels[][] = new int[levels.length][];
        copy2DArray(levels, tempLevels);
        //System.out.println("Interchanging: "+
        //       ((GraphNode)m_nodes.elementAt(levels[lindex+1][i])).ID+
        //       " & "+
        //	 ((GraphNode)m_nodes.elementAt(levels[lindex+1][(i+1)])).ID+
        //	 " at level "+(lindex+1) );
        int node1 = levels[lindex+1][i];
        int node2 = levels[lindex+1][i+1];
        levels[lindex+1][i+1] = node1;
        levels[lindex+1][i] = node2;
        
        for(int k=lindex+1; k<levels.length-1; k++)
          phaseID(k, levels);
        //System.out.println("Crossings temp:"+crossings(tempLevels)+
        //                   " graph:"+crossings(levels));
        if(crossings(levels)<=crossings(tempLevels)) {
          //System.out.println("Crossings temp: "+crossings(tempLevels)+
          //                   " Crossings levels: "+crossings(levels));
          copy2DArray(levels, tempLevels); } //printMatrices(levels); }
        else {
          copy2DArray(tempLevels, levels);
          levels[lindex+1][i+1] = node1;
          levels[lindex+1][i] = node2;
        }
        //System.out.println("Crossings after PhaseID of phaseIID, "+
        //                   "in iteration "+i+" of "+(colBC.length-1)+" at "+
        //                   lindex+", levels: "+crossings(levels)+
        //                   " temp: "+crossings(tempLevels));
        
        //tempLevels = new int[levels.length][];
        //copy2DArray(levels, tempLevels);
        for(int k=levels.length-2; k>=0; k--)
          phaseIU(k, levels);
        //System.out.println("Crossings temp:"+crossings(tempLevels)+
        //                   " graph:"+crossings(levels));
        //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 PhaseIU of phaseIID, in"+
        //                   " iteration "+i+" of "+(colBC.length-1)+" at "
        //		     +lindex+", levels: "+crossings(levels)+" temp: "+
        //                   crossings(tempLevels));
        //colBC = calcColBC(lindex, levels);
      }
    }
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  public void phaseIIU(final int lindex, final int levels[][]) {
    float rowBC[];
    rowBC = calcRowBC(lindex, levels);
    
    //System.out.println("Getting into phaseIIU");
    for(int i=0; i<rowBC.length-1; i++) {
      if(rowBC[i]==rowBC[i+1]) {
        //System.out.println("Crossings before begining of iteration: "+
        //                   crossings(levels));
        int tempLevels[][] = new int[levels.length][];
        copy2DArray(levels, tempLevels);
        //System.out.println("Interchanging: "+
        //          ((GraphNode)m_nodes.elementAt(levels[lindex][i])).ID+" & "+
        //          ((GraphNode)m_nodes.elementAt(levels[lindex][i+1])).ID+
        //          " at level "+(lindex+1) );
        int node1 = levels[lindex][i];
        int node2 = levels[lindex][i+1];
        levels[lindex][i+1] = node1;
        levels[lindex][i] = node2;
        
        for(int k=lindex-1; k>=0; k--)
          phaseIU(k, levels);
        if(crossings(levels)<=crossings(tempLevels)) { 
          //System.out.println("Crossings temp: "+crossings(tempLevels)+
          //                   " Crossings levels: "+crossings(levels));
          copy2DArray(levels, tempLevels); } //printMatrices(levels);
        else {
          copy2DArray(tempLevels, levels);
          levels[lindex][i+1] = node1;
          levels[lindex][i] = node2;
        }
        //System.out.println("Crossings after PhaseIU of PhaseIIU, in "+
        //                   "iteration "+i+" of "+(rowBC.length-1)+" at "
        //                   +lindex+", levels: "+crossings(levels)+
        //                   " temp: "+crossings(tempLevels));
        
        //tempLevels = new int[levels.length][];
        //copy2DArray(levels, tempLevels);
        for(int k=0; k<levels.length-1; k++) //lindex-1; k++)
          phaseID(k, levels);