hierarchicalbcengine.java

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

/*
 *    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 weka.core.FastVector;
import weka.gui.graphvisualizer.GraphNode;
import weka.gui.graphvisualizer.GraphEdge;

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

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

/**
 * 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 $Revision: 1.1 $ - 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() {
  //cannot perform a layout if no description of nodes and/or edges is provided
    if(m_nodes==null || m_edges==null)
      return; 
    
    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)