hierarchicalbcengine.java

Java 编写的多种数据挖掘算法 包括聚类、分类、预处理等

              //unlink source from the target
              graphMatrix[n][i] = 0;
              graphMatrix[i][n] = 0;
              continue;
              
            }
            
            int len = graphMatrix.length;
            int tempMatrix[][] =
            new int[graphMatrix.length+(nodesLevel[i]-nodesLevel[tempnode]-1)]
            [graphMatrix.length+(nodesLevel[i]-nodesLevel[tempnode]-1)];
            int level = nodesLevel[tempnode]+1;
            copyMatrix(graphMatrix, tempMatrix);
            
            String s1 = new String("S"+tempCnt++);
            //System.out.println("Adding dummy "+s1);
            m_nodes.addElement(new GraphNode(s1, s1, SINGULAR_DUMMY));
            
            int temp3 [] = new int[nodeLevels[level].length+1];
            System.arraycopy(nodeLevels[level], 0, temp3, 
                             0, nodeLevels[level].length);
            temp3[temp3.length-1] = m_nodes.size()-1;
            nodeLevels[level] = temp3;
            temp3 = new int[m_nodes.size()+1];
            System.arraycopy(nodesLevel, 0, temp3, 0, nodesLevel.length);
            temp3[m_nodes.size()-1] = level;
            nodesLevel = temp3;
            level++;
            //nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
            //System.out.println("len:"+len+"("+
            //                   ((GraphNode)m_nodes.elementAt(len)).ID+"),"+
            //                   nodesLevel[i]+","+nodesLevel[tempnode]);
            
            int m;
            for(m=len; m<len+nodesLevel[i]-nodesLevel[tempnode]-1-1; m++) {
              String s2 =  new String("S"+tempCnt++);
              //System.out.println("Adding dummy "+s2);
              m_nodes.addElement( new GraphNode(s2, s2, SINGULAR_DUMMY) );
              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;
              temp3 = new int[m_nodes.size()+1];
              System.arraycopy(nodesLevel, 0, temp3, 0, nodesLevel.length);
              temp3[m_nodes.size()-1] = level;
              nodesLevel = temp3;
              level++;
              //nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
              //System.out.println("modifying "+
              //                   ((GraphNode)nodes.elementAt(m)).ID+", "+
              //                   ((GraphNode)nodes.elementAt(m+1)).ID);
              tempMatrix[m][m+1]=tempMatrix[n][i]; //tempCnt++;
              if(m>len) {
                //System.out.println("modifying "+
                //                   ((GraphNode)nodes.elementAt(m)).ID+
                //                   ", "+((GraphNode)nodes.elementAt(m-1)).ID);
                tempMatrix[m][m-1]=-1*tempMatrix[n][i];
              }
            }
            //System.out.println("m "+((GraphNode)m_nodes.elementAt(m)).ID+
            //	   " i "+((GraphNode)m_nodes.elementAt(i)).ID+
            //     " tempnode "+((GraphNode)m_nodes.elementAt(tempnode)).ID+
            //	   " len "+((GraphNode)m_nodes.elementAt(len)).ID );
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(m)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(i)).ID);
            
            //temp[lastTempNodeCreated][targetNode]=temp[origNode][targetNode]
            tempMatrix[m][i]=tempMatrix[n][i];
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(tempnode)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(len)).ID);
            
            //temp[origNode][firstTempNodecreated] = temp[origNode][targetNode]
            tempMatrix[tempnode][len] =  tempMatrix[n][i];
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(len)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(tempnode)).ID);
            
            //temp[firstTempNodeCreated][origNode]  for reverse tracing
            tempMatrix[len][tempnode] = -1*tempMatrix[n][i]; 
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(i)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(m)).ID);
            
            //temp[targetNode][lastTempNodecreated]  for reverse tracing
            tempMatrix[i][m] = -1*tempMatrix[n][i];
            if(m>len) {
              //System.out.println("modifying "+
              //                   ((GraphNode)nodes.elementAt(m)).ID+
              //                   ", "+((GraphNode)nodes.elementAt(m-1)).ID);

              //temp[lastTempNodeCreated][secondlastNode] for reverse tracing
              //but only do this if more than 1 temp nodes are created
              tempMatrix[m][m-1] = -1*tempMatrix[n][i]; 
            }

            //temp[origNode][targetNode] = 0 unlinking as they have been
            tempMatrix[n][i]   = 0;
            
            //linked by a chain of temporary nodes now.
            tempMatrix[i][n]   = 0;
            
            graphMatrix = tempMatrix;
          }
          else {
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(i)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(n)).ID);
            //****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];
          }
      }
    }
    
  }
  
  
  /**
   * Returns the index of an element in a level.
   * Must never be called with the wrong element and
   * the wrong level, will throw an exception otherwise.
   * It takes as agrument the index of the element (in the m_nodes vector)
   * and the level it is supposed to be in (as each level contains the indices
   * of the nodes present in that level).
   */
  private int indexOfElementInLevel(int element, int level[]) throws Exception {
    int idx;
    
    for(int i=0; i<level.length; i++)
      if(level[i]==element)
        return i;
    throw new Exception("Error. Didn't find element "+
                        ((GraphNode)m_nodes.elementAt(element)).ID+
                        " in level. Inspect code for "+
                        "weka.gui.graphvisualizer.HierarchicalBCEngine");
  }
  
  
  
  /**
   * Computes the number of edge crossings in the whole graph
   * Takes as an argument levels of nodes. It is essentially the
   * same algorithm provided in Universitat des Saarlandes
   * technical report A03/94 by Georg Sander.
   */
  protected int crossings(final int levels[][]) {
    int sum=0;
    
    for(int i=0; i<levels.length-1; i++) {
      //System.out.println("*****************Processing level "+i+
      //                   "*****************************");
      MyList upper = new MyList(), lower = new MyList();
      MyListNode lastOcrnce[] = new MyListNode[m_nodes.size()];
      int edgeOcrnce[] = new int[m_nodes.size()];
      
      for(int j=0,uidx=0,lidx=0; j<(levels[i].length+levels[i+1].length); j++) {
        if((j%2==0 && uidx<levels[i].length) || lidx>=levels[i+1].length) {
          int k1=0, k2=0, k3=0;
          GraphNode n = (GraphNode) m_nodes.elementAt(levels[i][uidx]);
          //Deactivating and counting crossings for all edges ending in it
          //coming from bottom left
          if(lastOcrnce[levels[i][uidx]]!=null) {
            MyListNode temp = new MyListNode(-1); temp.next = upper.first;
            try {
              do {
                temp = temp.next;
                if(levels[i][uidx]==temp.n) {
                  k1 = k1+1;
                  k3 = k3+k2;
                  //System.out.println("Removing from upper: "+temp.n);
                  upper.remove(temp);
                }
                else
                  k2 = k2+1;
              } while(temp!=lastOcrnce[levels[i][uidx]]);
            }
            catch(NullPointerException ex) {
              System.out.println("levels[i][uidx]: "+levels[i][uidx]+
              " which is: "+((GraphNode)m_nodes.elementAt(levels[i][uidx])).ID+
              " temp: "+temp+
              " upper.first: "+upper.first);
            ex.printStackTrace();
            System.exit(-1);}
            
            lastOcrnce[levels[i][uidx]]=null;
            sum = sum + k1*lower.size() + k3;
          }
          //Activating all the edges going out towards the bottom 
          //and bottom right
          for(int k=0; k<n.edges.length; k++) {
            if(n.edges[k][1]>0)
              try {
                if( indexOfElementInLevel(n.edges[k][0], levels[i+1]) >= uidx) {
                  edgeOcrnce[n.edges[k][0]]=1;
                }
              }
              catch(Exception ex) {
                ex.printStackTrace();
              }
          }
          for(int k=0; k<levels[i+1].length; k++) {
            if(edgeOcrnce[levels[i+1][k]]==1) {
              MyListNode temp = new MyListNode(levels[i+1][k]); //new MyListNode(n.edges[k][0]);
              lower.add(temp);
              lastOcrnce[levels[i+1][k]] = temp;
              edgeOcrnce[levels[i+1][k]] = 0;
              //System.out.println("Adding to lower: "+levels[i+1][k]+
              //" which is: "+((GraphNode)m_nodes.elementAt(levels[i+1][k])).ID+
              //" first's n is: "+lower.first.n);
            }
            
          }
          uidx++;
        }
        else {
          int k1=0, k2=0, k3=0;
          GraphNode n = (GraphNode) m_nodes.elementAt(levels[i+1][lidx]);
          //Deactivating and counting crossings for all edges ending in it
          //coming from up and upper left
          if(lastOcrnce[levels[i+1][lidx]]!=null) {
            
            MyListNode temp = new MyListNode(-1); temp.next = lower.first;
            try {
              do {
                temp = temp.next;
                if(levels[i+1][lidx]==temp.n) {
                  k1 = k1+1;
                  k3 = k3+k2;
                  lower.remove(temp);
                  //System.out.println("Removing from lower: "+temp.n);
                }
                else
                  k2 = k2+1;
                //System.out.println("temp: "+temp+" lastOcrnce: "+
                //                   lastOcrnce[levels[i+1][lidx]]+" temp.n: "+
                //                   temp.n+" lastOcrnce.n: "+
                //                   lastOcrnce[levels[i+1][lidx]].n);
              } while(temp!=lastOcrnce[levels[i+1][lidx]]);
            }
            catch(NullPointerException ex) {
              System.out.print("levels[i+1][lidx]: "+levels[i+1][lidx]+
              " which is: "+
              ((GraphNode)m_nodes.elementAt(levels[i+1][lidx])).ID+
              " temp: "+temp);
              System.out.println(" lower.first: "+lower.first);
              ex.printStackTrace();
              System.exit(-1); 
            }
            
            lastOcrnce[levels[i+1][lidx]]=null;
            sum = sum + k1*upper.size() + k3;
          }
          
          //Activating all the edges going out towards the upper right
          for(int k=0; k<n.edges.length; k++) {
            if(n.edges[k][1]<0)
              try {
                if( indexOfElementInLevel(n.edges[k][0], levels[i]) > lidx) {
                  edgeOcrnce[n.edges[k][0]]=1;
                }
              }
              catch(Exception ex) {
                ex.printStackTrace();
              }
          }
          for(int k=0; k<levels[i].length; k++) {
            if(edgeOcrnce[levels[i][k]]==1) {
              MyListNode temp = new MyListNode(levels[i][k]);
              upper.add(temp);
              lastOcrnce[levels[i][k]]=temp;
              edgeOcrnce[levels[i][k]]=0;
              //System.out.println("Adding to upper: "+levels[i][k]+
              //	       " which is : "+
              //                ((GraphNode)m_nodes.elementAt(levels[i][k])).ID+
              //	       " from node: "+n.ID+", "+k+
              //	       " first's value: "+upper.first.n);
            }
          }
          lidx++;
        }
      }
      //System.out.println("Sum at the end is: "+sum);
    }
    
    return sum;
  }
  
  
  /**
   * The following two methods remove cycles from the graph.
   */
  protected void removeCycles() {
    //visited[x]=1 is only  visited AND visited[x]=2 means node is visited
    // and is on the current path
    int visited[]  = new int[m_nodes.size()];
    
    for(int i=0; i<graphMatrix.length; i++) {
      if(visited[i]==0){
        removeCycles2(i, visited);
        visited[i]=1;
      }
    }
  }
  
  /** This method should not be called directly. It should be called only from 
      to call removeCycles() */
  private void removeCycles2(int nindex, int visited[]) {
    visited[nindex]=2;
    for(int i=0; i<graphMatrix[nindex].length; i++) {
      if(graphMatrix[nindex][i]==DIRECTED)
        if(visited[i]==0) {
          removeCycles2(i, visited);
          visited[i]=1;
        }
        else if(visited[i]==2) {
          if(nindex==i) {
            graphMatrix[nindex][i]=0;
          }
          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;