sugiyamalayoutalgorithm.java

用JGraph编的软件

				);
			}

			// bottom up
			for (int i = levels.size() - 1; i >= 0; i--) {
				movementsCurrentLoop += moveToBarycenter(jgraph, levels, i);
			}

			if (verbose) {
				System.out.println("----------------Grid Pos after bottom up"
				/*#Frozen*/
				);
				displayGridPositions(levels);
				//displayDownPriorities();
				System.out.println("======================================="
				/*#Frozen*/
				);
			}

			this.updateProgress4Movements();
		}

	}

	protected int moveToBarycenter(
		JGraph jgraph,
		Vector levels,
		int levelIndex) {

		// Counter for the movements
		int movements = 0;

		// Get the current level
		Vector currentLevel = (Vector) levels.get(levelIndex);
		GraphModel model = jgraph.getModel();

		for (int currentIndexInTheLevel = 0;
			currentIndexInTheLevel < currentLevel.size();
			currentIndexInTheLevel++) {

			CellWrapper sourceWrapper =
				(CellWrapper) currentLevel.get(currentIndexInTheLevel);

			float gridPositionsSum = 0;
			float countNodes = 0;

			VertexView vertexView = sourceWrapper.getVertexView();
			Object vertex = vertexView.getCell();
			int portCount = model.getChildCount(vertex);

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

				Iterator edges = model.edges(port);
				while (edges.hasNext()) {
					Object edge = edges.next();

					// if it is a forward edge follow it
					Object neighborPort = null;
					if (port == model.getSource(edge)) {
						neighborPort = model.getTarget(edge);
					} else {
						if (port == model.getTarget(edge)) {
							neighborPort = model.getSource(edge);
						} else {
							continue;
						}
					}

					Object neighborVertex = model.getParent(neighborPort);

					VertexView neighborVertexView =
						(VertexView) jgraph.getGraphLayoutCache().getMapping(
							neighborVertex,
							false);
					
					if (neighborVertexView == null)
						continue;
							
					CellWrapper targetWrapper =
						(CellWrapper) neighborVertexView.getAttributes().get(
							SUGIYAMA_CELL_WRAPPER);

					if (targetWrapper == sourceWrapper)
						continue;
					if (targetWrapper == null
						|| targetWrapper.getLevel() == levelIndex)
						continue;

					gridPositionsSum += targetWrapper.getGridPosition();
					countNodes++;
				}
			}

			//----------------------------------------------------------
			// move node to new x coord
			//----------------------------------------------------------

			if (countNodes > 0) {
				float tmp = (gridPositionsSum / countNodes);
				int newGridPosition = Math.round(tmp);
				boolean toRight =
					(newGridPosition > sourceWrapper.getGridPosition());

				boolean moved = true;

				while (newGridPosition != sourceWrapper.getGridPosition()
					&& moved) {
					int tmpGridPos = sourceWrapper.getGridPosition();

					moved =
						move(
							toRight,
							currentLevel,
							currentIndexInTheLevel,
							sourceWrapper.getPriority());

					if (moved)
						movements++;

					if (verbose) {

						System
							.out
							.print(
								"try move at Level "
								+ levelIndex
								+ " with index "
								+ currentIndexInTheLevel
								+ " to "
								+ (toRight ? "Right" : "Left")
								+ " CurrentGridPos: "
								+ tmpGridPos
								+ " NewGridPos: "
								+ newGridPosition
								+ " exact: "
								+ NumberFormat.getInstance().format(tmp)
								+ "..." /*#Frozen*/
						);
						System.out.println(moved ? "success" /*#Frozen*/
						: "can't move" /*#Frozen*/
						);

					}
				}
			}
		}
		return movements;
	}

	/**@param  toRight <tt>true</tt> = try to move the currentWrapper to right; <tt>false</tt> = try to move the currentWrapper to left;
	 * @param  currentLevel Vector which contains the CellWrappers for the current level
	 * @param  currentIndexInTheLevel
	 * @param  currentPriority
	 * @param  currentWrapper The Wrapper
	 *
	 * @return The free GridPosition or -1 is position is not free.
	 */
	protected boolean move(
		boolean toRight,
		Vector currentLevel,
		int currentIndexInTheLevel,
		int currentPriority) {

		CellWrapper currentWrapper =
			(CellWrapper) currentLevel.get(currentIndexInTheLevel);

		boolean moved = false;
		int neighborIndexInTheLevel =
			currentIndexInTheLevel + (toRight ? 1 : -1);
		int newGridPosition =
			currentWrapper.getGridPosition() + (toRight ? 1 : -1);

		// is the grid position possible?

		if (0 > newGridPosition || newGridPosition >= gridAreaSize) {
			return false;
		}

		// if the node is the first or the last we can move
		if (toRight
			&& currentIndexInTheLevel == currentLevel.size() - 1
			|| !toRight
			&& currentIndexInTheLevel == 0) {

			moved = true;

		} else {
			// else get the neighbor and ask his gridposition
			// if he has the requested new grid position
			// check the priority

			CellWrapper neighborWrapper =
				(CellWrapper) currentLevel.get(neighborIndexInTheLevel);

			int neighborPriority = neighborWrapper.getPriority();

			if (neighborWrapper.getGridPosition() == newGridPosition) {
				if (neighborPriority >= currentPriority) {
					return false;
				} else {
					moved =
						move(
							toRight,
							currentLevel,
							neighborIndexInTheLevel,
							currentPriority);
				}
			} else {
				moved = true;
			}
		}

		if (moved) {
			currentWrapper.setGridPosition(newGridPosition);
		}
		return moved;
	}

	/** This Method draws the graph. For the horizontal position
	 *  we are using the grid position from each graphcell.
	 *  For the vertical position we are using the level position.
	 *
	 */
	protected void drawGraph(
		JGraph jgraph,
		Vector levels,
		Point min,
		Point spacing) {
		// paint the graph

		Map viewMap = new Hashtable();

		for (int rowCellCount = 0;
			rowCellCount < levels.size();
			rowCellCount++) {
			Vector level = (Vector) levels.get(rowCellCount);

			for (int colCellCount = 0;
				colCellCount < level.size();
				colCellCount++) {
				CellWrapper wrapper = (CellWrapper) level.get(colCellCount);
				VertexView view = wrapper.vertexView;

				// remove the temp objects
				/* While the Algorithm is running we are putting some
				 *  attributeNames to the MyGraphCells. This method
				 *  cleans this objects from the MyGraphCells.
				 *
				 */
				view.getAttributes().remove(SUGIYAMA_CELL_WRAPPER);
				view.getAttributes().remove(SUGIYAMA_VISITED);
				wrapper.vertexView = null;

				// get the bounds from the cellView
				if (view == null)
					continue;
				Rectangle bounds = (Rectangle) view.getBounds().clone();

				// adjust
				bounds.x = min.x + spacing.x * wrapper.getGridPosition();
				bounds.y = min.y + spacing.y * rowCellCount;

				Object cell = view.getCell();
				Map map = GraphConstants.createMap();
				GraphConstants.setBounds(map, bounds);

				viewMap.put(cell, map);

			}

		}
		jgraph.getGraphLayoutCache().edit(viewMap, null, null, null);
	}

	/** cell wrapper contains all values
	 *  for one node
	 */
	class CellWrapper implements Comparable {

		/** sum value for edge Crosses
		 */
		private double edgeCrossesIndicator = 0;
		/** counter for additions to the edgeCrossesIndicator
		 */
		private int additions = 0;
		/** the vertical level where the cell wrapper is inserted
		 */
		int level = 0;
		/** current position in the grid
		 */
		int gridPosition = 0;
		/** priority for movements to the barycenter
		 */
		int priority = 0;
		/** reference to the wrapped cell
		 */
		VertexView vertexView = null;

		/** creates an instance and memorizes the parameters
		 *
		 */
		CellWrapper(
			int level,
			double edgeCrossesIndicator,
			VertexView vertexView) {
			this.level = level;
			this.edgeCrossesIndicator = edgeCrossesIndicator;
			this.vertexView = vertexView;
			additions++;
		}

		/** returns the wrapped cell
		 */
		VertexView getVertexView() {
			return vertexView;
		}

		/** resets the indicator for edge crosses to 0
		 */
		void resetEdgeCrossesIndicator() {
			edgeCrossesIndicator = 0;
			additions = 0;
		}

		/** retruns the average value for the edge crosses indicator
		 *
		 *  for the wrapped cell
		 *
		 */

		double getEdgeCrossesIndicator() {
			if (additions == 0)
				return 0;
			return edgeCrossesIndicator / additions;
		}

		/** Addes a value to the edge crosses indicator
		 *  for the wrapped cell
		 *
		 */
		void addToEdgeCrossesIndicator(double addValue) {
			edgeCrossesIndicator += addValue;
			additions++;
		}
		/** gets the level of the wrapped cell
		 */
		int getLevel() {
			return level;
		}

		/** gets the grid position for the wrapped cell
		 */
		int getGridPosition() {
			return gridPosition;
		}

		/** Sets the grid position for the wrapped cell
		 */
		void setGridPosition(int pos) {
			this.gridPosition = pos;
		}

		/** increments the the priority of this cell wrapper.
		 *
		 *  The priority was used by moving the cell to its
		 *  barycenter.
		 *
		 */

		void incrementPriority() {
			priority++;
		}

		/** returns the priority of this cell wrapper.
		 *
		 *  The priority was used by moving the cell to its
		 *  barycenter.
		 */
		int getPriority() {
			return priority;
		}

		/**
		 * @see java.lang.Comparable#compareTo(Object)
		 */
		public int compareTo(Object compare) {
			if (((CellWrapper) compare).getEdgeCrossesIndicator()
				== this.getEdgeCrossesIndicator())
				return 0;

			double compareValue =
				(((CellWrapper) compare).getEdgeCrossesIndicator()
					- this.getEdgeCrossesIndicator());

			return (int) (compareValue * 1000);

		}
	}
}