sugiyamalayoutalgorithm.java

用JGraph编的软件

	 *  @param graphCell    The Graph Cell
	 */
	protected void fillLevels(
		JGraph jgraph,
		Vector levels,
		int level,
		VertexView vertexView) {
		// precondition control
		if (vertexView == null)
			return;

		// be sure that a Vector container exists for the current level
		if (levels.size() == level)
			levels.insertElementAt(new Vector(), level);

		// if the cell already visited return
		if (vertexView.getAttributes().get(SUGIYAMA_VISITED) != null) {
			return;
		}

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

		// put the current node into the current level
		// get the Level Vector
		Vector vecForTheCurrentLevel = (Vector) levels.get(level);

		// Create a wrapper for the node
		int numberForTheEntry = vecForTheCurrentLevel.size();

		CellWrapper wrapper =
			new CellWrapper(level, numberForTheEntry, vertexView);

		// put the Wrapper in the LevelVector
		vecForTheCurrentLevel.add(wrapper);

		// concat the wrapper to the cell for an easy access
		vertexView.getAttributes().put(SUGIYAMA_CELL_WRAPPER, wrapper);

		// if the Cell has no Ports we can return, there are no relations
		Object vertex = vertexView.getCell();
		GraphModel model = jgraph.getModel();
		int portCount = model.getChildCount(vertex);

		// iterate any NodePort
		for (int i = 0; i < portCount; i++) {

			Object port = model.getChild(vertex, i);

			// iterate any Edge in the port
			Iterator itrEdges = model.edges(port);

			while (itrEdges.hasNext()) {
				Object edge = itrEdges.next();

				// if the Edge is a forward edge we should follow this edge
				if (port == model.getSource(edge)) {
					Object targetPort = model.getTarget(edge);
					Object targetVertex = model.getParent(targetPort);
					VertexView targetVertexView =
						(VertexView) jgraph.getGraphLayoutCache().getMapping(
							targetVertex,
							false);
					fillLevels(jgraph, levels, (level + 1), targetVertexView);
				}
			}
		}

		if (vecForTheCurrentLevel.size() > gridAreaSize) {
			gridAreaSize = vecForTheCurrentLevel.size();
		}

	}

	/** calculates the minimum for the paint area.
	 *
	 */
	protected Point findMinimumAndSpacing(
		CellView[] graphCellViews,
		Point spacing) {
		try {

			// variables
			/* represents the minimum x value for the paint area
			 */
			int min_x = 1000000;

			/* represents the minimum y value for the paint area
			 */
			int min_y = 1000000;

			// find the maximum & minimum coordinates

			for (int i = 0; i < graphCellViews.length; i++) {

				// the cellView and their bounds
				CellView cellView = graphCellViews[i];

				if (cellView == null)
					continue;
					
				Rectangle cellViewBounds = cellView.getBounds();

				// checking min area
				try {
					if (cellViewBounds.x < min_x)
						min_x = cellViewBounds.x;
					if (cellViewBounds.y < min_y)
						min_y = cellViewBounds.y;
					/*
					if (cellViewBounds.width > spacing.x)
						spacing.x = cellViewBounds.width;
					if (cellViewBounds.height > spacing.y)
						spacing.y = cellViewBounds.height;
						*/

				} catch (Exception e) {
					System.err.println("---------> ERROR in calculateValues."
					/*#Frozen*/
					);
					e.printStackTrace();
				}
			}
			// if the cell sice is bigger than the userspacing
			// dublicate the spacingfactor
			return new Point(min_x, min_y);

		} catch (Exception e) {
			e.printStackTrace();
		}
		return null;
	}

	/** Updates the progress based on the movements count
	 *
	 */
	protected void updateProgress4Movements() {
		// adds the current loop count
		movements.add(new Integer(movementsCurrentLoop));
		iteration++;

		// if the current loop count is higher than the max movements count
		// memorize the new max
		if (movementsCurrentLoop > movementsMax) {
			movementsMax = movementsCurrentLoop;
		}

		// Calculate the new progress
		if (movements.size() > 1) {
			dlgProgress.setValue(movements.size() - 1);
		}
	}

	protected void solveEdgeCrosses(JGraph jgraph, Vector levels) {
		dlgProgress.setMessage(Translator.getString("SolvingCrossOverPoints"
		/*#Finished:Original="solving cross over points ..."*/
		));

		movements = new Vector(100);
		movementsCurrentLoop = -1;
		movementsMax = Integer.MIN_VALUE;
		iteration = 0;

		while (movementsCurrentLoop != 0) {

			// reset the movements per loop count
			movementsCurrentLoop = 0;

			if (verbose) {
				System.out.println("---------------------------- vor Sort"
				/*#Frozen*/
				);
				displayEdgeCrossesValues(levels);
			}

			// top down
			for (int i = 0; i < levels.size() - 1; i++) {
				movementsCurrentLoop
					+= solveEdgeCrosses(jgraph, true, levels, i);
			}

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

			if (verbose) {
				System.out.println("---------------------------- nach Sort"
				/*#Frozen*/
				);
				displayEdgeCrossesValues(levels);
			}

			updateProgress4Movements();
		}
		dlgProgress.setToMaximum();
	}

	/**
	 *  @return movements
	 */
	protected int solveEdgeCrosses(
		JGraph jgraph,
		boolean down,
		Vector levels,
		int levelIndex) {
		// Get the current level
		Vector currentLevel = (Vector) levels.get(levelIndex);
		int movements = 0;

		// restore the old sort
		Object[] levelSortBefore = currentLevel.toArray();

		// new sort
		Collections.sort(currentLevel);

		// test for movements
		for (int j = 0; j < levelSortBefore.length; j++) {
			if (((CellWrapper) levelSortBefore[j]).getEdgeCrossesIndicator()
				!= ((CellWrapper) currentLevel.get(j))
					.getEdgeCrossesIndicator()) {
				movements++;

			}
		}

		GraphModel model = jgraph.getModel();

		// Collecations Sort sorts the highest value to the first value
		for (int j = currentLevel.size() - 1; j >= 0; j--) {
			CellWrapper sourceWrapper = (CellWrapper) currentLevel.get(j);

			VertexView sourceView = sourceWrapper.getVertexView();

			Object sourceVertex = sourceView.getCell();
			int sourcePortCount = model.getChildCount(sourceVertex);

			for (int k = 0; k < sourcePortCount; k++) {
				Object sourcePort = model.getChild(sourceVertex, k);

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

					// if it is a forward edge follow it
					Object targetPort = null;
					if (down && sourcePort == model.getSource(edge)) {
						targetPort = model.getTarget(edge);
					}
					if (!down && sourcePort == model.getTarget(edge)) {
						targetPort = model.getSource(edge);
					}
					if (targetPort == null)
						continue;

					Object targetCell = model.getParent(targetPort);
					VertexView targetVertexView =
						(VertexView) jgraph.getGraphLayoutCache().getMapping(
							targetCell,
							false);

					if (targetVertexView == null)
						continue;

					CellWrapper targetWrapper =
						(CellWrapper) targetVertexView.getAttributes().get(
							SUGIYAMA_CELL_WRAPPER);

					// do it only if the edge is a forward edge to a deeper level
					if (down
						&& targetWrapper != null
						&& targetWrapper.getLevel() > levelIndex) {
						targetWrapper.addToEdgeCrossesIndicator(
							sourceWrapper.getEdgeCrossesIndicator());
					}
					if (!down
						&& targetWrapper != null
						&& targetWrapper.getLevel() < levelIndex) {
						targetWrapper.addToEdgeCrossesIndicator(
							sourceWrapper.getEdgeCrossesIndicator());
					}
				}
			}
		}

		return movements;
	}

	protected void moveToBarycenter(
		JGraph jgraph,
		CellView[] allSelectedViews,
		Vector levels) {

		//================================================================
		// iterate any ReViewNodePort
		GraphModel model = jgraph.getModel();
		for (int i = 0; i < allSelectedViews.length; i++) {
			if (!(allSelectedViews[i] instanceof VertexView))
				continue;

			VertexView vertexView = (VertexView) allSelectedViews[i];

			CellWrapper currentwrapper =
				(CellWrapper) vertexView.getAttributes().get(
					SUGIYAMA_CELL_WRAPPER);

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

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

				// iterate any Edge in the port

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

					Object neighborPort = null;
					// if the Edge is a forward edge we should follow this edge
					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
						|| neighborVertexView == vertexView)
						continue;

					CellWrapper neighborWrapper =
						(CellWrapper) neighborVertexView.getAttributes().get(
							SUGIYAMA_CELL_WRAPPER);

					if (currentwrapper == null
						|| neighborWrapper == null
						|| currentwrapper.level == neighborWrapper.level)
						continue;

					currentwrapper.priority++;

				}
			}
		}

		//================================================================
		for (int j = 0; j < levels.size(); j++) {
			Vector level = (Vector) levels.get(j);
			for (int i = 0; i < level.size(); i++) {
				// calculate the initial Grid Positions 1, 2, 3, .... per Level
				CellWrapper wrapper = (CellWrapper) level.get(i);
				wrapper.setGridPosition(i);
			}
		}

		if (verbose) {
			System.out.println("----------------Grid Pos before top down"
			/*#Frozen*/
			);
			displayPriorities(levels);
			displayGridPositions(levels);
			System.out.println("======================================="
			/*#Frozen*/
			);
		}

		movements = new Vector(100);
		movementsCurrentLoop = -1;
		movementsMax = Integer.MIN_VALUE;
		iteration = 0;

		//int movements = 1;

		while (movementsCurrentLoop != 0) {

			// reset movements
			movementsCurrentLoop = 0;

			// top down
			for (int i = 1; i < levels.size(); i++) {
				movementsCurrentLoop += moveToBarycenter(jgraph, levels, i);
			}

			if (verbose) {
				System.out.println("----------------Grid Pos after top down"
				/*#Frozen*/
				);
				displayGridPositions(levels);
				System.out.println("======================================="
				/*#Frozen*/