sugiyamalayoutalgorithm.java

用JGraph编的软件

// This file is part of the Echidna project
// (C) 2002 Forschungszentrum Informatik (FZI) Karlsruhe
// Please visit our website at http://echidna.sf.net
package org.jgraph.layout;

import java.awt.Frame;
import java.awt.Point;
import java.awt.Rectangle;
import java.text.NumberFormat;
import java.util.Collections;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Properties;
import java.util.Vector;

import javax.swing.JOptionPane;

import org.jgraph.JGraph;
import org.jgraph.graph.CellView;
import org.jgraph.graph.GraphConstants;
import org.jgraph.graph.GraphModel;
import org.jgraph.graph.VertexView;
import org.jgraph.pad.resources.Translator;

/**
 * Arranges the nodes with the Sugiyama Layout Algorithm.<br>
 *
 * <a href="http://plg.uwaterloo.ca/~itbowman/CS746G/Notes/Sugiyama1981_MVU/">
 *  Link to the algorithm</a>
 *
 *<br>
 *<br>
 * @author Sven Luzar<br>
 * @version 1.0 init
 */
public class SugiyamaLayoutAlgorithm implements LayoutAlgorithm {

	/** Field for debug output
	 */
	protected final boolean verbose = false;

	/** Const to add Attributes at the Nodes
	 *
	 */
	public static final String SUGIYAMA_VISITED = "SugiyamaVisited" /*#Frozen*/;

	/** Const to add the Cell Wrapper to the Nodes
	 */
	public static final String SUGIYAMA_CELL_WRAPPER =
		"SugiyamaCellWrapper" /*#Frozen*/;

	/** represents the size of the grid in horizontal grid elements
	 *
	 */
	protected int gridAreaSize = Integer.MIN_VALUE;

	/** Progressbar is shown while the algorithm is running
	 */
	protected ProgressDialog dlgProgress =
		new ProgressDialog(
			(Frame) null,
			Translator.getString("Progress") + ":",
			false);
	/* #Finished */

	/** A vector with Integer Objects. The Vector contains the
	 *  history of movements per loop
	 *  It was needed for the progress dialog
	 */
	Vector movements = null;
	/** Represents the movements in the current loop.
	 *  It was needed for the progress dialog
	 */
	int movementsCurrentLoop = -1;
	/** Represents the maximum of movements in the current loop.
	 *  It was needed for the progress dialog
	 */
	int movementsMax = Integer.MIN_VALUE;
	/** Represents the current loop number
	 *  It was needed for the progress dialog
	 */
	int iteration = 0;

	/**
	 * Implementation.
	 *
	 * First of all the Algorithm searches the roots from the
	 * Graph. Starting from this roots the Algorithm creates
	 * levels and stores them in the member <code>levels</code>.
	 * The Member levels contains Vector Objects and the Vector per level
	 * contains Cell Wrapper Objects. After that the Algorithm
	 * tries to solve the edge crosses from level to level and
	 * goes top down and bottom up. After minimization of the
	 * edge crosses the algorithm moves each node to its
	 * bary center. Last but not Least the method draws the Graph.
	 *
	 * @see LayoutAlgorithm
	 *
	 */
	public void perform(
		JGraph jgraph,
		boolean applyToAll,
		Properties configuration) {

		Object[] selectedCells =
			(applyToAll ? jgraph.getRoots() : jgraph.getSelectionCells());
		CellView[] selectedCellViews =
			jgraph.getGraphLayoutCache().getMapping(selectedCells);

		Point spacing = new Point();
		/*  The Algorithm distributes the nodes on a grid.
		 *  For this grid you can configure the horizontal spacing.
		 *  This field specifies the configured value
		 *
		 */
		spacing.x =
			Integer.parseInt(
				configuration.getProperty(
					SugiyamaLayoutController.KEY_HORIZONTAL_SPACING));

		/*  The Algorithm distributes the nodes on a grid.
		 *  For this grid you can configure the vertical spacing.
		 *  This field specifies the configured value
		 *
		 */

		spacing.y =
			Integer.parseInt(
				configuration.getProperty(
					SugiyamaLayoutController.KEY_VERTICAL_SPACING));

		// set the progress dialog visible
		dlgProgress.setVisible(true);

		// search all roots
		Vector roots = searchRoots(jgraph, selectedCellViews);

		// return if no root found
		if (roots.size() == 0)
			return;

		// create levels
		Vector levels = fillLevels(jgraph, selectedCellViews, roots);

		// solves the edge crosses
		solveEdgeCrosses(jgraph, levels);

		// move all nodes into the barycenter
		moveToBarycenter(jgraph, selectedCellViews, levels);

		Point min = findMinimumAndSpacing(selectedCellViews, spacing);

		// draw the graph in the window
		drawGraph(jgraph, levels, min, spacing);

		// clean temp values from the nodes / cells
		// the clean up was made in drawGraph
		//cleanUp(selectedCellViews);

		// sets the progress dialog unvisible
		dlgProgress.setVisible(false);
	}

	/** Debugdisplay for the edge crosses indicators on the System out
	 */
	protected void displayEdgeCrossesValues(Vector levels) {
		System.out.println("----------------Edge Crosses Indicator Values"
		/*#Frozen*/
		);

		for (int i = 0; i < levels.size() - 1; i++) {
			// Get the current level
			Vector currentLevel = (Vector) levels.get(i);
			System.out.print("Level (" + i + "):" /*#Frozen*/
			);
			for (int j = 0; j < currentLevel.size(); j++) {
				CellWrapper sourceWrapper = (CellWrapper) currentLevel.get(j);

				System
					.out
					.print(
						NumberFormat.getNumberInstance().format(
							sourceWrapper.getEdgeCrossesIndicator())
						+ " - " /*#Frozen*/
				);
			}
			System.out.println();
		}
	}

	/** Debugdisplay for the grid positions on the System out
	 */
	protected void displayGridPositions(Vector levels) {

		System.out.println("----------------GridPositions" /*#Frozen*/
		);

		for (int i = 0; i < levels.size() - 1; i++) {
			// Get the current level
			Vector currentLevel = (Vector) levels.get(i);
			System.out.print("Level (" + i + "):" /*#Frozen*/
			);
			for (int j = 0; j < currentLevel.size(); j++) {
				CellWrapper sourceWrapper = (CellWrapper) currentLevel.get(j);
				System
					.out
					.print(
						NumberFormat.getNumberInstance().format(
							sourceWrapper.getGridPosition())
						+ " - " /*#Frozen*/
				);
			}
			System.out.println();
		}
	}

	/** Debugdisplay for the priorities on the System out
	 */
	protected void displayPriorities(Vector levels) {

		System.out.println("----------------down Priorities" /*#Frozen*/
		);

		for (int i = 0; i < levels.size() - 1; i++) {
			// Get the current level
			Vector currentLevel = (Vector) levels.get(i);
			System.out.print("Level (" + i + "):" /*#Frozen*/
			);
			for (int j = 0; j < currentLevel.size(); j++) {
				CellWrapper sourceWrapper = (CellWrapper) currentLevel.get(j);
				System.out.print(sourceWrapper.getPriority() +
				/*" (" +
				                   sourceWrapper.nearestDownNeighborLevel + ") " +*/
				" - " /*#Frozen*/
				);
			}
			System.out.println();
		}
	}

	/** Searches all Roots for the current Graph
	 *  First the method marks any Node as not visited.
	 *  Than calls searchRoots(MyGraphCell) for each
	 *  not visited Cell.
	 *  The Roots are stored in the Vector named roots
	 *
	 * 	@return returns a Vector with the roots
	 *  @see #searchRoots(JGraph, CellView[])
	 */
	protected Vector searchRoots(JGraph jgraph, CellView[] selectedCellViews) {

		// get all cells and relations
		Vector vertexViews = new Vector(selectedCellViews.length);
		Vector roots = new Vector();

		// first: mark all as not visited
		// O(allCells&Edges)
		for (int i = 0; i < selectedCellViews.length; i++) {
			if (selectedCellViews[i] instanceof VertexView) {
				VertexView vertexView = (VertexView) selectedCellViews[i];
				vertexView.getAttributes().remove(SUGIYAMA_VISITED);
				vertexViews.add(selectedCellViews[i]);
			}
		}

		// O(graphCells)
		for (int i = 0; i < vertexViews.size(); i++) {
			VertexView vertexView = (VertexView) vertexViews.get(i);
			if (vertexView.getAttributes().get(SUGIYAMA_VISITED) == null) {
				searchRoots(jgraph, vertexView, roots);
			}
		}

		// Error Msg if the graph has no roots
		if (roots.size() == 0) {
			JOptionPane
				.showMessageDialog(
					null,
					Translator.getString("TheGraphIsNotADAG"
			/*#Finished:Original="The Graph is not a DAG. Can't use Sugiyama Algorithm!"*/
			), null, JOptionPane.ERROR_MESSAGE);
		}
		return roots;
	}

	/** Searches Roots for the current Cell.
	 *
	 *  Therefore he looks at all Ports from the Cell.
	 *  At the Ports he looks for Edges.
	 *  At the Edges he looks for the Target.
	 *  If the Ports of the current Cell contains the target ReViewNodePort
	 *  he follows the edge to the source and looks at the
	 *  Cell for this source.
	 *
	 *  @param graphCell The current cell
	 */
	protected void searchRoots(
		JGraph jgraph,
		VertexView vertexViewToInspect,
		Vector roots) {
		// the node already visited
		if (vertexViewToInspect.getAttributes().get(SUGIYAMA_VISITED)
			!= null) {
			return;
		}

		// mark as visited for cycle tests
		vertexViewToInspect.getAttributes().put(
			SUGIYAMA_VISITED,
			new Boolean(true));

		GraphModel model = jgraph.getModel();

		// get all Ports and search the relations at the ports
		//List vertexPortViewList = new ArrayList() ;

		Object vertex = vertexViewToInspect.getCell();

		int portCount = model.getChildCount(vertex);
		for (int j = 0; j < portCount; j++) {
			Object port = model.getChild(vertex, j);

			// Test all relations for where
			// the current node is a target node
			// for roots

			boolean isRoot = true;
			Iterator itrEdges = model.edges(port);
			while (itrEdges.hasNext()) {
				Object edge = itrEdges.next();

				// if the current node is a target node
				// get the source node and test
				// the source node for roots

				if (model.getTarget(edge) == port) {
					Object sourcePort = model.getSource(edge);

					Object sourceVertex = model.getParent(sourcePort);

					CellView sourceVertexView =
						jgraph.getGraphLayoutCache().getMapping(
							sourceVertex,
							false);
					if (sourceVertexView instanceof VertexView) {
						searchRoots(
							jgraph,
							(VertexView) sourceVertexView,
							roots);
						isRoot = false;
					}
				}
			}
			// The current node is never a Target Node
			// -> The current node is a root node
			if (isRoot) {
				roots.add(vertexViewToInspect);
			}
		}
	}

	/** Method fills the levels and stores them in the member levels.
	
	 *  Each level was represended by a Vector with Cell Wrapper objects.
	 *  These Vectors are the elements in the <code>levels</code> Vector.
	 *
	 */
	protected Vector fillLevels(
		JGraph jgraph,
		CellView[] selectedCellViews,
		Vector rootVertexViews) {
		Vector levels = new Vector();

		// mark as not visited
		// O(allCells)
		for (int i = 0; i < selectedCellViews.length; i++) {
			CellView cellView = selectedCellViews[i];

			// more stabile
			if (cellView == null)
				continue;

			cellView.getAttributes().remove(SUGIYAMA_VISITED);
		}

		Enumeration enumRoots = rootVertexViews.elements();
		while (enumRoots.hasMoreElements()) {
			VertexView vertexView = (VertexView) enumRoots.nextElement();
			fillLevels(jgraph, levels, 0, vertexView);
		}

		return levels;

	}

	/** Fills the Vector for the specified level with a wrapper
	 *  for the MyGraphCell. After that the method called for
	 *  each neighbor graph cell.
	 *
	 *  @param level        The level for the graphCell