hierarchicalbcengine.java

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

			tempMatrix[m][i]=tempMatrix[n][i];  //temp[lastTempNodeCreated][targetNode]=temp[origNode][targetNode]
			//System.out.println("modifying "+((GraphNode)nodes.elementAt(tempnode)).ID+
			//	       ", "+((GraphNode)nodes.elementAt(len)).ID);
			tempMatrix[tempnode][len] = 
			    tempMatrix[n][i]; //temp[origNode][firstTempNodecreated] = temp[origNode][targetNode]
			//System.out.println("modifying "+((GraphNode)nodes.elementAt(len)).ID+
			//	       ", "+((GraphNode)nodes.elementAt(tempnode)).ID);
			tempMatrix[len][tempnode] = 
			    -1*tempMatrix[n][i]; //temp[firstTempNodeCreated][origNode]  for reverse tracing
			//System.out.println("modifying "+((GraphNode)nodes.elementAt(i)).ID+
			//	       ", "+((GraphNode)nodes.elementAt(m)).ID);
			tempMatrix[i][m]          = 
			    -1*tempMatrix[n][i]; //temp[targetNode][lastTempNodecreated]  for reverse tracing
			if(m>len) {
			    //System.out.println("modifying "+((GraphNode)nodes.elementAt(m)).ID+
		  	    //	   ", "+((GraphNode)nodes.elementAt(m-1)).ID);
			    tempMatrix[m][m-1]    =       //temp[lastTempNodeCreated][secondlastNode] for reverse tracing 
				-1*tempMatrix[n][i];      //but only do this if more than 1 temp nodes are created 
			}
			tempMatrix[n][i]   = 0;                //temp[origNode][targetNode] = 0 unlinking as they have been 
			tempMatrix[i][n]   = 0;                // linked by a chain of temporary nodes now.
			
			
			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() {
	int visited[]  = new int[m_nodes.size()]; //visited[x]=1 is only  visited AND visited[x]=2 means node is visited  
	                                          // and is on the current path
	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. Better 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;
	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);