weka.gui.graphvisualizer
Class HierarchicalBCEngine

java.lang.Object
  weka.gui.graphvisualizer.HierarchicalBCEngine

All Implemented Interfaces:

GraphConstants, LayoutEngine

public class HierarchicalBCEngine

extends java.lang.Object

implements GraphConstants, LayoutEngine

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.

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.

Version:

1.0 - 24 Apr 2003 - Initial version (Ashraf M. Kibriya)

Author:

Ashraf M. Kibriya (amk14@cs.waikato.ac.nz)

Nested Class Summary

private class	HierarchicalBCEngine.MyList The following classes implement a double linked list to be used in the crossings function.
private class	HierarchicalBCEngine.MyListNode

Field Summary

protected int[][]	graphMatrix Interconnection matrix for the graph
protected FastVector	layoutCompleteListeners FastVector containing listeners for layoutCompleteEvent generated by this LayoutEngine
protected boolean	m_completeReLayout This tells the the LayoutGraph method if a completeReLayout should be performed when it is called.
protected javax.swing.JPanel	m_controlsPanel The panel containing extra options, specific to this LayoutEngine, for greater control over layout of the graph
protected FastVector	m_edges FastVector containing nodes and edges
protected javax.swing.JCheckBox	m_jCbEdgeConcentration controls edge concentration by concentrating multilple singular dummy child nodes into one plural dummy child node
protected javax.swing.JRadioButton	m_jRbBottomup
protected javax.swing.JRadioButton	m_jRbNaiveLayout
protected javax.swing.JRadioButton	m_jRbPriorityLayout
protected javax.swing.JRadioButton	m_jRbTopdown
protected int	m_nodeHeight The nodeWidth and nodeHeight
protected FastVector	m_nodes FastVector containing nodes and edges
protected int	m_nodeWidth The nodeWidth and nodeHeight
protected javax.swing.JProgressBar	m_progress The progress bar to show the progress of the layout process
protected int[][]	nodeLevels Array containing the indices of nodes in each level.
private int	origNodesSize This contains the original size of the nodes vector when it was passed in through the constructor, before adding all the dummy vertices

Fields inherited from interface weka.gui.graphvisualizer.GraphConstants

DIRECTED, DOUBLE, NORMAL, PLURAL_DUMMY, REVERSED, SINGULAR_DUMMY

Constructor Summary

HierarchicalBCEngine()
SimpleConstructor If we want to instantiate the class first, and if information for nodes and edges is not available.

HierarchicalBCEngine(FastVector nodes, FastVector edges, int nodeWidth, int nodeHeight)
Constructor - takes in FastVectors of nodes and edges, and the initial width and height of a node

HierarchicalBCEngine(FastVector nodes, FastVector edges, int nodeWidth, int nodeHeight, boolean edgeConcentration)
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.

Method Summary

void	addLayoutCompleteEventListener(LayoutCompleteEventListener l) Method to add a LayoutCompleteEventListener
protected void	assignLevels(int[] levels, int depth, int i, int j) This method assigns a vertical level to each node.
protected float[]	calcColBC(int lindex, int[][] levels) See Sugiyama et al. 1981 (full reference give at top)
protected float[]	calcRowBC(int lindex, int[][] levels) See Sugiyama et al. 1981 (full reference give at top)
protected void	clearTemps_and_EdgesFromNodes() 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
protected void	copy2DArray(int[][] from, int[][] to) Copies one array of type int[][] to another.
protected void	copyMatrix(int[][] from, int[][] to) Copies one Matrix of type int[][] to another.
protected int	crossings(int[][] levels) Computes the number of edge crossings in the whole graph Takes as an argument levels of nodes.
void	fireLayoutCompleteEvent(LayoutCompleteEvent e) Fires a LayoutCompleteEvent.
javax.swing.JPanel	getControlPanel() 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.
javax.swing.JProgressBar	getProgressBar() Returns a handle to the progressBar of this LayoutEngine.
private int	indexOfElementInLevel(int element, int[] level) Returns the index of an element in a level.
protected static void	isort(int[] level, float[] BC) This methods sorts the vertices in level[] according to their barycenters in BC[], using insertion sort.
void	layoutGraph() 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.
protected int	lBCenter(int lindex, int eindex, int[] horPositions)
protected int	lConnectivity(int lindex, int eindex)
protected void	makeGUIPanel(boolean edgeConc) This methods makes the gui extra controls panel "m_controlsPanel"
protected void	makeProperHierarchy()
private int[][]	minimizeCrossings(boolean reversed, int[][] nodeLevels) 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.
protected void	naiveLayout() This method lays out the vertices horizontally, in each level.
protected void	phaseID(int lindex, int[][] levels) See Sugiyama et al. 1981 (full reference give at top) lindex is the index of the level we want to process.
void	phaseIID(int lindex, int[][] levels) See Sugiyama et al. 1981 (full reference give at top)
void	phaseIIU(int lindex, int[][] levels) See Sugiyama et al. 1981 (full reference give at top)
void	phaseIU(int lindex, int[][] levels) See Sugiyama et al. 1981 (full reference give at top) lindex is the index of the level we want to process.
protected void	printMatrices(int[][] levels) Prints out the interconnection matrix at each level.
protected void	priorityLayout1() This method lays out the vertices horizontally, in each level.
private void	priorityLayout2(int[] level, int[] priorities, int[] bCenters, int[] horPositions) This method is used by priorityLayout1().
protected void	processGraph() This method makes the "graphMatrix" interconnection matrix for the graph given by m_nodes and m_edges vectors.
protected void	removeCycles() The following two methods remove cycles from the graph.
private void	removeCycles2(int nindex, int[] visited) This method should not be called directly.
private void	removeGaps(int[] nodesLevel) This method removes gaps from the graph.
private void	removeGapsWithEdgeConcentration(int[] nodesLevel) This method removes gaps from the graph.
void	removeLayoutCompleteEventListener(LayoutCompleteEventListener e) Method to remove a LayoutCompleteEventListener.
void	setNodesEdges(FastVector nodes, FastVector edges) Sets the nodes and edges for this LayoutEngine.
void	setNodeSize(int nodeWidth, int nodeHeight) Sets the size of a node.
private void	tempMethod(int[] horPositions)
protected int	uBCenter(int lindex, int eindex, int[] horPositions)
protected int	uConnectivity(int lindex, int eindex)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

m_nodes

protected FastVector m_nodes

FastVector containing nodes and edges

m_edges

protected FastVector m_edges

FastVector containing nodes and edges

layoutCompleteListeners

protected FastVector layoutCompleteListeners

FastVector containing listeners for layoutCompleteEvent generated by this LayoutEngine

graphMatrix

protected int[][] graphMatrix

Interconnection matrix for the graph

nodeLevels

protected int[][] nodeLevels

Array containing the indices of nodes in each level. The nodeLevels.length is equal to the number of levels

m_nodeWidth

protected int m_nodeWidth

The nodeWidth and nodeHeight

m_nodeHeight

protected int m_nodeHeight

The nodeWidth and nodeHeight

m_jRbNaiveLayout

protected javax.swing.JRadioButton m_jRbNaiveLayout

m_jRbPriorityLayout

protected javax.swing.JRadioButton m_jRbPriorityLayout

m_jRbTopdown

protected javax.swing.JRadioButton m_jRbTopdown

m_jRbBottomup

protected javax.swing.JRadioButton m_jRbBottomup

m_jCbEdgeConcentration

protected javax.swing.JCheckBox m_jCbEdgeConcentration

controls edge concentration by concentrating multilple singular dummy child nodes into one plural dummy child node

m_controlsPanel

protected javax.swing.JPanel m_controlsPanel

The panel containing extra options, specific to this LayoutEngine, for greater control over layout of the graph

m_progress

protected javax.swing.JProgressBar m_progress

The progress bar to show the progress of the layout process

m_completeReLayout

protected boolean m_completeReLayout

This tells the the LayoutGraph method if a completeReLayout should be performed when it is called.

origNodesSize

private int origNodesSize

This contains the original size of the nodes vector when it was passed in through the constructor, before adding all the dummy vertices

Constructor Detail

HierarchicalBCEngine

public HierarchicalBCEngine(FastVector nodes,
                            FastVector edges,
                            int nodeWidth,
                            int nodeHeight)

Constructor - takes in FastVectors of nodes and edges, and the initial width and height of a node

HierarchicalBCEngine

public HierarchicalBCEngine(FastVector nodes,
                            FastVector edges,
                            int nodeWidth,
                            int nodeHeight,
                            boolean edgeConcentration)

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.

Parameters:

nodes - - FastVector containing all the nodes

edges - - FastVector containing all the edges

nodeWidth - - A node's allowed width

nodeHeight - - A node's allowed height

edgeConcentration - - True: if want to concentrate edges, False: otherwise

HierarchicalBCEngine

public HierarchicalBCEngine()

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

Method Detail

makeGUIPanel

protected void makeGUIPanel(boolean edgeConc)

This methods makes the gui extra controls panel "m_controlsPanel"

getControlPanel

public javax.swing.JPanel getControlPanel()

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.

Specified by:

getControlPanel in interface LayoutEngine

getProgressBar

public javax.swing.JProgressBar getProgressBar()

Returns a handle to the progressBar of this LayoutEngine.

Specified by:

getProgressBar in interface LayoutEngine

setNodesEdges

public void setNodesEdges(FastVector nodes,
                          FastVector edges)

Sets the nodes and edges for this LayoutEngine. Must be used if the class created by simple HierarchicalBCEngine() constructor.

Specified by:

setNodesEdges in interface LayoutEngine

Parameters:

nodes - - FastVector containing all the nodes

edges - - FastVector containing all the edges

setNodeSize

public void setNodeSize(int nodeWidth,
                        int nodeHeight)

Sets the size of a node. This method must be used if the class created by simple HierarchicalBCEngine() constructor.

Specified by:

setNodeSize in interface LayoutEngine

Parameters:

nodeWidth - - A node's allowed width

nodeHeight - - A node's allowed height

addLayoutCompleteEventListener

public void addLayoutCompleteEventListener(LayoutCompleteEventListener l)

Method to add a LayoutCompleteEventListener

Specified by:

addLayoutCompleteEventListener in interface LayoutEngine

Parameters:

l - - Listener to receive the LayoutCompleteEvent by this class.

removeLayoutCompleteEventListener

public void removeLayoutCompleteEventListener(LayoutCompleteEventListener e)

Method to remove a LayoutCompleteEventListener.

Specified by:

removeLayoutCompleteEventListener in interface LayoutEngine

Parameters:

e - - The LayoutCompleteEventListener to remove.

fireLayoutCompleteEvent

public void fireLayoutCompleteEvent(LayoutCompleteEvent e)

Fires a LayoutCompleteEvent.

Specified by:

fireLayoutCompleteEvent in interface LayoutEngine

Parameters:

e - - The LayoutCompleteEvent to fire

layoutGraph

public void layoutGraph()

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.

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.

Specified by:

layoutGraph in interface LayoutEngine

clearTemps_and_EdgesFromNodes

protected void clearTemps_and_EdgesFromNodes()

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

processGraph

protected void processGraph()

This method makes the "graphMatrix" interconnection matrix for the graph given by m_nodes and m_edges vectors. The matix is used by other methods.

makeProperHierarchy

protected void makeProperHierarchy()

removeGaps

private void removeGaps(int[] nodesLevel)

This method removes gaps from the graph. It doesn't perform any concentration. It takes as an argument of int[] of length m_nodes.size() containing the level of each node.

removeGapsWithEdgeConcentration

private void removeGapsWithEdgeConcentration(int[] nodesLevel)

This method removes gaps from the graph. It tries to minimise the number of edges by concentrating multiple dummy nodes from the same parent and on the same vertical level into one. It takes as an argument of int[] of length m_nodes.size() containing the level of each node.

indexOfElementInLevel

private int indexOfElementInLevel(int element,
                                  int[] level)
                           throws java.lang.Exception

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).

Throws:

java.lang.Exception

crossings

protected int crossings(int[][] levels)

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.

removeCycles

protected void removeCycles()

The following two methods remove cycles from the graph.

removeCycles2

private void removeCycles2(int nindex,
                           int[] visited)

This method should not be called directly. Better to call removeCycles()

assignLevels

protected void assignLevels(int[] levels,
                            int depth,
                            int i,
                            int j)

This method assigns a vertical level to each node. See makeProperHierarchy() to see how to use it.

minimizeCrossings

private int[][] minimizeCrossings(boolean reversed,
                                  int[][] nodeLevels)

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.

phaseID

protected void phaseID(int lindex,
                       int[][] levels)

See Sugiyama et al. 1981 (full reference give at top) lindex is the index of the level we want to process. In this method we'll sort the vertices at the level one below lindex according to their UP-barycenters (or column barycenters).

phaseIU

public void phaseIU(int lindex,
                    int[][] levels)

See Sugiyama et al. 1981 (full reference give at top) lindex is the index of the level we want to process. In this method we'll sort the vertices at the level lindex according to their DOWN-barycenters (or row barycenters).

phaseIID

public void phaseIID(int lindex,
                     int[][] levels)

See Sugiyama et al. 1981 (full reference give at top)

phaseIIU

public void phaseIIU(int lindex,
                     int[][] levels)

See Sugiyama et al. 1981 (full reference give at top)

calcRowBC

protected float[] calcRowBC(int lindex,
                            int[][] levels)

See Sugiyama et al. 1981 (full reference give at top)

calcColBC

protected float[] calcColBC(int lindex,
                            int[][] levels)

See Sugiyama et al. 1981 (full reference give at top)

printMatrices

protected void printMatrices(int[][] levels)

Prints out the interconnection matrix at each level. See Sugiyama et al. 1981 (full reference give at top)

isort

protected static void isort(int[] level,
                            float[] BC)

This methods sorts the vertices in level[] according to their barycenters in BC[], using insertion sort. It, however, doesn't touch the vertices with barycenter equal to zero.

copyMatrix

protected void copyMatrix(int[][] from,
                          int[][] to)

Copies one Matrix of type int[][] to another.

copy2DArray

protected void copy2DArray(int[][] from,
                           int[][] to)

Copies one array of type int[][] to another.

naiveLayout

protected void naiveLayout()

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.

uConnectivity

protected int uConnectivity(int lindex,
                            int eindex)

lConnectivity

protected int lConnectivity(int lindex,
                            int eindex)

uBCenter

protected int uBCenter(int lindex,
                       int eindex,
                       int[] horPositions)

lBCenter

protected int lBCenter(int lindex,
                       int eindex,
                       int[] horPositions)

tempMethod

private void tempMethod(int[] horPositions)

priorityLayout1

protected void priorityLayout1()

This method lays out the vertices horizontally, in each level. See Sugiyama et al. 1981 for full reference.

priorityLayout2

private void priorityLayout2(int[] level,
                             int[] priorities,
                             int[] bCenters,
                             int[] horPositions)

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.