hierarchicalbcengine.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

	    //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=0; i<nodeLevels.length; i++) {
	    int count=0;
	    for(int j=0; j<nodeLevels[i].length; j++) {
		horPositions[nodeLevels[i][j]]=j;   
		count++;
	    }
	    if(count>maxCount)
		maxCount=count;
	}
	//fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
	int priorities[], BC[];
	//System.out.println("********Going from 2 to n********");
	for(int i=1; i<nodeLevels.length; i++) {
	    priorities = new int[nodeLevels[i].length];
	    BC = new int[nodeLevels[i].length];
	    for(int j=0; j<nodeLevels[i].length; j++) {
		if( ((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID.startsWith("S") )
		    priorities[j] = maxCount+1;
		else
		    priorities[j] = uConnectivity(i, j);
		BC[j] = uBCenter(i, j, horPositions);
	    }
	    //for(int j=0; j<nodeLevels[i].length; j++)
	    //  System.out.println("Level: "+(i+1)+" Node: "
	    //	       +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
	    //            +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
	    //	       +horPositions[nodeLevels[i][j]]);
	    priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
	    //repaint
	    //try {
	    //	tempMethod(horPositions);
	    //	fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
	    //	Thread.sleep(1000);
	    //} catch(InterruptedException ie) { ie.printStackTrace(); }
	    
	    //for(int j=0; j<nodeLevels[i].length; j++)
	    //    System.out.println("Level: "+(i+1)+" Node: "
	    //		       +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
	    //		       +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
	    //		       +horPositions[nodeLevels[i][j]]);
	}

	//System.out.println("********Going from n-1 to 1********");
	for(int i=nodeLevels.length-2; i>=0; i--) {
	    priorities = new int[nodeLevels[i].length]; 
	    BC = new int[nodeLevels[i].length];
	    for(int j=0; j<nodeLevels[i].length; j++) {
		if( ((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID.startsWith("S") )
		    priorities[j] = maxCount+1;
		else
		    priorities[j] = lConnectivity(i, j);
		BC[j] = lBCenter(i, j, horPositions); //, priorities[j]); 
	    }
	    priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
	    //repaint();
	    //try {
	    //	tempMethod(horPositions);
	    //	fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );		
	    //	Thread.sleep(1000);
	    //} catch(InterruptedException ie) { ie.printStackTrace(); }
	    
	    //for(int j=0; j<nodeLevels[i].length; j++)
	    //    System.out.println("Level: "+(i+1)+" Node: "
	    //		       +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
	    //		       +" lConnectivity: "+priorities[j]+" lBC: "+BC[j]+" position: "
	    //		       +horPositions[nodeLevels[i][j]]);
	}

	//System.out.println("********Going from 2 to n again********");
	for(int i=2; i<nodeLevels.length; i++) {
	    priorities = new int[nodeLevels[i].length];
	    BC = new int[nodeLevels[i].length];
	    for(int j=0; j<nodeLevels[i].length; j++) {
		if( ((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID.startsWith("S") )
		    priorities[j] = maxCount+1;
		else
		    priorities[j] = uConnectivity(i, j);
		BC[j] = uBCenter(i, j, horPositions);
	    }
	    //for(int j=0; j<nodeLevels[i].length; j++)
	    //    System.out.println("Level: "+(i+1)+" Node: "
	    //		       +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
	    //		       +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
	    //		       +horPositions[nodeLevels[i][j]]);
	    priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
	    //repaint();
	    //try {
	    //	tempMethod(horPositions);
	    //	fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );		
	    //	Thread.sleep(1000);
	    //} catch(InterruptedException ie) { ie.printStackTrace(); }
	    //for(int j=0; j<nodeLevels[i].length; j++)
	    //    System.out.println("Level: "+(i+1)+" Node: "
	    //		       +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
	    //		       +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
	    //		       +horPositions[nodeLevels[i][j]]);
	}
	
	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;
	    }
	}
	//setAppropriateSize();
    }

    /**
     * This method is used by priorityLayout1(). It should
     * not be called directly.
     * This method does the actual moving of the vertices in each level
     * based on their priorities and barycenters.
     */
    private void priorityLayout2(int level[], int priorities[], int bCenters[], int horPositions[]) {
	int descOrder[] = new int[priorities.length];

	//Getting the indices of priorities in descending order
	descOrder[0]=0;
	for(int i=0; i<priorities.length-1; i++) {
	    int j=i;
	    int temp=i+1;
	    
	    while( j>-1 && priorities[descOrder[j]]<priorities[temp] ) {
		descOrder[j+1] = descOrder[j];
		j--;
	    }
	    j++;
	    descOrder[j] = temp;
	}
	
	//System.out.println("\nPriorities:");
	//for(int i=0; i<priorities.length; i++)
	//    System.out.print(priorities[i]+" ");
	//System.out.println("\nDescOrder:");
	//for(int i=0; i<descOrder.length; i++)
	//    System.out.print(descOrder[i]+" ");

	for(int k=0; k<descOrder.length; k++)
	    for(int i=0; i<descOrder.length; i++) {
		
		int leftCount=0, rightCount=0, leftNodes[], rightNodes[];
		for(int j=0; j<priorities.length; j++) {
		    if( horPositions[level[descOrder[i]]] > horPositions[level[j]] )
			leftCount++;
		    else if( horPositions[level[descOrder[i]]] < horPositions[level[j]] )
			rightCount++;
		}
		leftNodes = new int[leftCount];
		rightNodes = new int[rightCount];

		for(int j=0, l=0, r=0; j<priorities.length; j++)
		    if( horPositions[level[descOrder[i]]] > horPositions[level[j]] )
			leftNodes[l++]=j;
		    else if( horPositions[level[descOrder[i]]] < horPositions[level[j]] )
			rightNodes[r++]=j;
		
		
		//****Moving left	    
		while( Math.abs(horPositions[level[descOrder[i]]]-1-bCenters[descOrder[i]]) < 
		       Math.abs(horPositions[level[descOrder[i]]]-bCenters[descOrder[i]]) ) {
		    
		    //****Checking if it can be moved to left
		    int temp = horPositions[level[descOrder[i]]];
		    boolean cantMove=false;
		    
		    for(int j=leftNodes.length-1; j>=0; j--) {
			if(temp-horPositions[level[leftNodes[j]]] > 1)
			    break;
			else if(priorities[descOrder[i]]<=priorities[leftNodes[j]])
			    { cantMove=true; break; }
			else
			    temp = horPositions[level[leftNodes[j]]];
		    }
		    //if(horPositions[level[descOrder[i]]]-1==horPositions[level[leftNodes[j]]])
		    //    cantMove = true;
		    if(cantMove)
			break;
		    
		    temp = horPositions[level[descOrder[i]]]-1;
		    //****moving other vertices to left
		    for(int j=leftNodes.length-1; j>=0; j--) {
			if(temp==horPositions[level[leftNodes[j]]])
			    {   //System.out.println("Moving "+((Node)m_nodes.elementAt(level[leftNodes[j]])).ID+" from "
				//		  +horPositions[level[leftNodes[j]]]+" to "
				//		  +(horPositions[level[leftNodes[j]]]-1) );
				horPositions[level[leftNodes[j]]] = temp = horPositions[level[leftNodes[j]]]-1; }
			
		    }
		    //System.out.println("Moving main "+((GraphNode)m_nodes.element