hierarchicalbcengine.java

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

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */


/*
 *    HierarchicalBCEngine.java
 *    Copyright (C) 2003 Ashraf M. Kibriya
 *
 */
package weka.gui.graphvisualizer;

import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.BorderFactory;
import javax.swing.ButtonGroup;
import javax.swing.JCheckBox;
import javax.swing.JPanel;
import javax.swing.JProgressBar;
import javax.swing.JRadioButton;

import weka.core.FastVector;

/**
 * This class lays out the vertices of a graph in a
 * hierarchy of vertical levels, with a number of nodes
 * in each level. The number of levels is the depth of
 * the deepest child reachable from some parent at level
 * 0. It implements a layout technique as described by
 * K. Sugiyama, S. Tagawa, and M. Toda. in "Methods for 
 * visual understanding of hierarchical systems", IEEE 
 * Transactions on Systems, Man and Cybernetics, 
 * SMC-11(2):109-125, Feb. 1981.
 * <p>There have been a few modifications made, however.
 * The crossings function is changed as it was non-linear
 * in time complexity. Furthermore, we don't have any
 * interconnection matrices for each level, instead we 
 * just have one big interconnection matrix for the
 * whole graph and a int[][] array which stores the
 * vertices present in each level.
 *
 * @author Ashraf M. Kibriya ([e-mail])
 * @version 1.0 - 24 Apr 2003 - Initial version (Ashraf M. Kibriya)
 *
 */
public class HierarchicalBCEngine implements GraphConstants, LayoutEngine {

    /** FastVector containing nodes and edges */
    protected FastVector m_nodes, m_edges;
    /**  FastVector containing listeners for 
	 layoutCompleteEvent generated by this 
	 LayoutEngine  */
    protected FastVector layoutCompleteListeners;
    /**   Interconnection matrix for the graph  */
    protected int graphMatrix[][];
    /** Array containing the indices of nodes in each level.
	The nodeLevels.length is equal to the number of levels  */
    protected int nodeLevels[][];
    /** The nodeWidth and nodeHeight */
    protected int m_nodeWidth, m_nodeHeight;

    /* The following radio buttons control the
       way the layout is performed. If any 
       of the following is changed then we
       need to perform a complete relayout
    */
    protected JRadioButton m_jRbNaiveLayout;
    protected JRadioButton m_jRbPriorityLayout;
    protected JRadioButton m_jRbTopdown;
    protected JRadioButton m_jRbBottomup;
    /** controls edge concentration by concentrating multilple singular dummy child nodes 
	into one plural dummy child node*/
    protected JCheckBox m_jCbEdgeConcentration;
    /** The panel containing extra options, 
	specific to this LayoutEngine, for 
        greater control over layout of the graph */
    protected JPanel m_controlsPanel;
    /** The progress bar to show the progress
        of the layout process */
    protected JProgressBar m_progress;
    /** This tells the the LayoutGraph method if
        a completeReLayout should be performed 
	when it is called. */
    protected boolean m_completeReLayout=false;
    /** This contains the original size of the nodes vector
        when it was passed in through the constructor, before
        adding all the dummy vertices */
    private int origNodesSize;
    
    /** Constructor - takes in FastVectors of nodes and edges, and the initial width and height of a node
     */
    public HierarchicalBCEngine(FastVector nodes, FastVector edges, int nodeWidth, int nodeHeight) {
	m_nodes = nodes; m_edges = edges; m_nodeWidth = nodeWidth; m_nodeHeight = nodeHeight;
	makeGUIPanel(false);
    }

    /** Constructor - takes in FastVectors of nodes and edges, the initial width and height of a node,
	and a boolean value to indicate if the edges should be concentrated.
	@param nodes - FastVector containing all the nodes
	@param edges - FastVector containing all the edges
	@param nodeWidth - A node's allowed width
	@param nodeHeight - A node's allowed height
	@param edgeConcentration - True: if want to concentrate edges, False: otherwise
     */
    public HierarchicalBCEngine(FastVector nodes, FastVector edges, int nodeWidth, int nodeHeight, boolean edgeConcentration) {
	m_nodes = nodes; m_edges = edges; m_nodeWidth = nodeWidth; m_nodeHeight = nodeHeight;
	makeGUIPanel(edgeConcentration);
    }

    /** SimpleConstructor 
	If we want to instantiate the class first, and if information for
	nodes and edges is not available. However, we would have to manually
	provide all the information later on by calling setNodesEdges and 
	setNodeSize methods
     */
    public HierarchicalBCEngine() {   }

    /**
       This methods makes the gui extra controls panel "m_controlsPanel"
     */
    protected void makeGUIPanel(boolean edgeConc) {
	m_jRbNaiveLayout = new JRadioButton("Naive Layout");
	m_jRbPriorityLayout = new JRadioButton("Priority Layout");
	ButtonGroup bg = new ButtonGroup();
	bg.add(m_jRbNaiveLayout);
	bg.add(m_jRbPriorityLayout);
	m_jRbPriorityLayout.setSelected(true);
	
	ActionListener a = new ActionListener() {
		                  public void actionPerformed(ActionEvent ae) {
				      m_completeReLayout=true;
				  }
	                   };

	m_jRbTopdown = new JRadioButton("Top Down");
	m_jRbBottomup = new JRadioButton("Bottom Up");
	m_jRbTopdown.addActionListener(a);
	m_jRbBottomup.addActionListener(a);
	bg = new ButtonGroup();
	bg.add(m_jRbTopdown);
	bg.add(m_jRbBottomup);
	m_jRbBottomup.setSelected(true);

	m_jCbEdgeConcentration = new JCheckBox("With Edge Concentration", edgeConc);
	m_jCbEdgeConcentration.setSelected(edgeConc);
	m_jCbEdgeConcentration.addActionListener(a);

	JPanel jp1 = new JPanel( new GridBagLayout() );
	GridBagConstraints gbc = new GridBagConstraints();
	gbc.gridwidth = gbc.REMAINDER;
	gbc.anchor = gbc.NORTHWEST;
	gbc.weightx = 1;
	gbc.fill = gbc.HORIZONTAL;
	jp1.add(m_jRbNaiveLayout, gbc);
	jp1.add(m_jRbPriorityLayout, gbc);
	jp1.setBorder( BorderFactory.createTitledBorder("Layout Type") );

	JPanel jp2 = new JPanel( new GridBagLayout() );
	jp2.add(m_jRbTopdown, gbc);
	jp2.add(m_jRbBottomup, gbc);
	jp2.setBorder( BorderFactory.createTitledBorder("Layout Method") );


	m_progress = new JProgressBar(0, 11);
	m_progress.setBorderPainted(false);
	m_progress.setStringPainted(true);
	m_progress.setString("");

	m_progress.setValue(0);
	
	m_controlsPanel = new JPanel( new GridBagLayout() );
	m_controlsPanel.add(jp1, gbc);
	m_controlsPanel.add(jp2, gbc);
	m_controlsPanel.add(m_jCbEdgeConcentration, gbc);
    }

    
    /** This method returns a handle to the extra
	controls panel, so that the visualizing
	class can add it to some of it's own
	gui panel. 
    */
    public JPanel getControlPanel() {
	return m_controlsPanel;
    }
    
    /** Returns a handle to the progressBar
	of this LayoutEngine.
    */
    public JProgressBar getProgressBar() {
	return m_progress;
    }
    
    /** Sets the nodes and edges for this LayoutEngine. 
	Must be used if the class created by simple 
	HierarchicalBCEngine() constructor.
	@param nodes - FastVector containing all the nodes
	@param edges - FastVector containing all the edges
     */
    public void setNodesEdges(FastVector nodes, FastVector edges) {
	m_nodes = nodes; m_edges = edges;
    }
 
    /**
     * Sets the size of a node. This method must be 
     *	used if the class created by simple 
     *	HierarchicalBCEngine() constructor.
     *	@param nodeWidth - A node's allowed width
     *	@param nodeHeight - A node's allowed height
     */   
    public void setNodeSize(int nodeWidth, int nodeHeight) {
	m_nodeWidth = nodeWidth;
	m_nodeHeight = nodeHeight;
    }

    /**
     * Method to add a LayoutCompleteEventListener
     * @param l - Listener to receive the LayoutCompleteEvent by this 
     *            class.
     */
    public void addLayoutCompleteEventListener(LayoutCompleteEventListener l) {
	if(layoutCompleteListeners==null)
	    layoutCompleteListeners = new FastVector();
	layoutCompleteListeners.addElement(l);
    }

    /**
     * Method to remove a LayoutCompleteEventListener.
     * @param e - The LayoutCompleteEventListener to remove.       
     */
    public void removeLayoutCompleteEventListener(LayoutCompleteEventListener e){
	if(layoutCompleteListeners!=null) {
	    LayoutCompleteEventListener l;
	    
	    for(int i=0; i<layoutCompleteListeners.size(); i++) {
		l = (LayoutCompleteEventListener) layoutCompleteListeners.elementAt(i);
		if(l==e) {
		    layoutCompleteListeners.removeElementAt(i);
		    return;
		}
	    }
	    System.err.println("layoutCompleteListener to be remove not present");  
	}
	else
	    System.err.println("layoutCompleteListener to be remove not present"); 
    }

    /**
     * Fires a LayoutCompleteEvent.
     * @param e - The LayoutCompleteEvent to fire
     */
    public void fireLayoutCompleteEvent(LayoutCompleteEvent e) {
	if(layoutCompleteListeners!=null && layoutCompleteListeners.size()!=0) {
	    LayoutCompleteEventListener l;
	    
	    for(int i=0; i<layoutCompleteListeners.size(); i++) {
		l = (LayoutCompleteEventListener) layoutCompleteListeners.elementAt(i);
		l.layoutCompleted(e);
	    }	
	}
    }


    /**
     * This method does a complete layout of the graph which includes
     * removing cycles, assigning levels to nodes, reducing edge crossings
     * and laying out the vertices horizontally for better visibility.
     * The removing of cycles and assignment of levels is only performed 
     * if hasn't been performed earlier or if some layout option has been 
     * changed and it is necessary to do so. It is necessary to do so,
     * if the user selects/deselects edge concentration or topdown/bottomup
     * options. 
     * <p> The layout is performed in a separate thread and the progress
     * bar of the class is updated for each of the steps as the process
     * continues.
     */
    public void layoutGraph() {
	if(m_nodes==null || m_edges==null)
	    return;  //cannot perform a layout if no description of nodes and/or edges is provided

	Thread th = new Thread() {
		public void run() {
		    m_progress.setBorderPainted(true);
		    if(nodeLevels==null) {
			makeProperHierarchy();
		    }
		    else if(m_completeReLayout==true)
			{ clearTemps_and_EdgesFromNodes(); makeProperHierarchy(); m_completeReLayout=false;}

		    //minimizing crossings
		    if(m_jRbTopdown.isSelected()) {
			int crossbefore=crossings(nodeLevels), crossafter=0, i=0;
			do {
			    m_progress.setValue(i+4);
			    m_progress.setString("Minimizing Crossings: Pass"+(i+1));
			    if(i!=0)
				crossbefore = crossafter;
			    nodeLevels = minimizeCrossings(false, nodeLevels);
			    crossafter = crossings(nodeLevels);
			    i++;
			}
			while(crossafter<crossbefore && i<6);
		    }
		    else {
			int crossbefore=crossings(nodeLevels), crossafter=0, i=0;
			do {
			    m_progress.setValue(i+4);
			    m_progress.setString("Minimizing Crossings: Pass"+(i+1));
			    if(i!=0)
				crossbefore = crossafter;
			    nodeLevels = minimizeCrossings(true, nodeLevels);
			    crossafter = crossings(nodeLevels);
			    i++;
			}
			while(crossafter<crossbefore && i<6);
		    }
		    //System.out.println("\nCrossings at the end "+crossings(nodeLevels)+"\n---------------------------------");
		    
		    m_progress.setValue(10);
		    m_progress.setString("Laying out vertices");
		    //Laying out graph
		    if(m_jRbNaiveLayout.isSelected())
			naiveLayout();
		    else
			priorityLayout1();
		    m_progress.setValue(11);
		    m_progress.setString("Layout Complete");
		    m_progress.repaint();

		fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
		m_progress.setValue(0);
		m_progress.setString("");
		m_progress.setBorderPainted(false);
		}
	    };
	th.start();
    }

    /**
     * This method removes the temporary nodes that were
     * added to fill in the gaps, and removes all edges 
     * from all nodes in their edges[][] array