Attachment #91437 for bug #221214

Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

Lines 40-45 Link Here

(-)src/org/eclipse/draw2d/graph/CompoundDirectedGraphLayout.java (+1 lines)
40	void init() {	40	void init() {
41	steps.add(new TransposeMetrics());	41	steps.add(new TransposeMetrics());
42	steps.add(new CompoundBreakCycles());	42	steps.add(new CompoundBreakCycles());
		43	steps.add(new SpaceOutEdges());
43	steps.add(new RouteEdges());	44	steps.add(new RouteEdges());
44	steps.add(new ConvertCompoundGraph());	45	steps.add(new ConvertCompoundGraph());
45	steps.add(new InitialRankSolver());	46	steps.add(new InitialRankSolver());

Lines 61-70 Link Here

(-)src/org/eclipse/draw2d/graph/PopulateRanks.java (-4 / +4 lines)
61	Node prev = null, cur;	61	Node prev = null, cur;
62	for (int n = 0; n < rank.size(); n++) {	62	for (int n = 0; n < rank.size(); n++) {
63	cur = rank.getNode(n);	63	cur = rank.getNode(n);
64	if (cur instanceof VirtualNode)	64	cur.left = prev;
65	((VirtualNode)cur).left = prev;	65	if (prev != null) {
66	if (prev instanceof VirtualNode)	66	prev.right = cur;
67	((VirtualNode)prev).right = cur;	67	}
68	prev = cur;	68	prev = cur;
69	}	69	}
70	}	70	}

Lines 75-81 Link Here

(-)src/org/eclipse/draw2d/graph/Rank.java (-1 / +3 lines)
75	for (int i = 0; i < size(); i++) {	75	for (int i = 0; i < size(); i++) {
76	Node n = getNode(i);	76	Node n = getNode(i);
77	n.y = location;	77	n.y = location;
78	n.height = rowHeight;	78	if (n instanceof VirtualNode) {
		79	n.height = rowHeight;
		80	}
79	}	81	}
80	}	82	}
81		83

Lines 1-5 Link Here

(-)src/org/eclipse/draw2d/graph/Edge.java (-1 / +29 lines)
1	/*******************************************************************************	1	/*******************************************************************************
2	* Copyright (c) 2003, 2005 IBM Corporation and others.	2	* Copyright (c) 2003, 2008 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials	3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0	4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at	5	* which accompanies this distribution, and is available at
Lines 39-44 Link Here
39	* @since 2.1.2	39	* @since 2.1.2
40	*/	40	*/
41	public class Edge {	41	public class Edge {
		42
		43	public static final int DEFAULT_ROUTING_STYLE = 0;
		44	public static final int ORTHOGONAL_ROUTING_STYLE = 1;
42		45
43	int cut;	46	int cut;
44		47
Lines 92-97 Link Here
92		95
93	private PointList points;	96	private PointList points;
94		97
		98	private int routingStyle = DEFAULT_ROUTING_STYLE;
		99
95	/**	100	/**
96	* The source Node.	101	* The source Node.
97	*/	102	*/
Lines 322-327 Link Here
322	this.padding = padding;	327	this.padding = padding;
323	}	328	}
324		329
		330	/**
		331	* Sets the points for the edge
		332	* @param points the points
		333	* @since 3.4
		334	*/
325	void setPoints(PointList points) {	335	void setPoints(PointList points) {
326	this.points = points;	336	this.points = points;
327	start = points.getFirstPoint();	337	start = points.getFirstPoint();
Lines 377-380 Link Here
377	this.width = width;	387	this.width = width;
378	}	388	}
379		389
		390	/**
		391	* Gets the routing style constant
		392	* @return the routing style
		393	* @since 3.4
		394	*/
		395	public int getRoutingStyle() {
		396	return routingStyle;
		397	}
		398
		399	/**
		400	* Sets the routing style constant
		401	* @param style the style
		402	* @since 3.4
		403	*/
		404	public void setRoutingStyle(int style) {
		405	this.routingStyle = style;
		406	}
		407
380	}	408	}

Lines 46-51 Link Here

(-)src/org/eclipse/draw2d/graph/Node.java (+2 lines)
46	* @since 2.1.2	46	* @since 2.1.2
47	*/	47	*/
48	public class Node {	48	public class Node {
		49
		50	Node left, right;
49		51
50	Object workingData[] = new Object[3];	52	Object workingData[] = new Object[3];
51	int workingInts[] = new int[4];	53	int workingInts[] = new int[4];

Lines 75-80 Link Here

(-)src/org/eclipse/draw2d/graph/DirectedGraphLayout.java (+1 lines)
75	void init() {	75	void init() {
76	steps.add(new TransposeMetrics());	76	steps.add(new TransposeMetrics());
77	steps.add(new BreakCycles());	77	steps.add(new BreakCycles());
		78	steps.add(new SpaceOutEdges());
78	steps.add(new RouteEdges());	79	steps.add(new RouteEdges());
79	steps.add(new InitialRankSolver());	80	steps.add(new InitialRankSolver());
80	steps.add(new TightSpanningTreeSolver());	81	steps.add(new TightSpanningTreeSolver());

Lines 1-5 Link Here

(-)src/org/eclipse/draw2d/graph/VirtualNode.java (-3 / +1 lines)
1	/*******************************************************************************	1	/*******************************************************************************
2	* Copyright (c) 2003, 2005 IBM Corporation and others.	2	* Copyright (c) 2003, 2008 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials	3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0	4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at	5	* which accompanies this distribution, and is available at
Lines 19-26 Link Here
19	*/	19	*/
20	public class VirtualNode extends Node {	20	public class VirtualNode extends Node {
21		21
22	Node left, right;
23
24	/**	22	/**
25	* The next node.	23	* The next node.
26	*/	24	*/

Lines 1-5 Link Here

(-)src/org/eclipse/draw2d/graph/RouteEdges.java (-34 / +56 lines)
1	/*******************************************************************************	1	/*******************************************************************************
2	* Copyright (c) 2003, 2005 IBM Corporation and others.	2	* Copyright (c) 2003, 2008 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials	3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0	4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at	5	* which accompanies this distribution, and is available at
Lines 10-16 Link Here
10	*******************************************************************************/	10	*******************************************************************************/
11	package org.eclipse.draw2d.graph;	11	package org.eclipse.draw2d.graph;
12		12
13	import org.eclipse.draw2d.geometry.Insets;
14	import org.eclipse.draw2d.geometry.Point;	13	import org.eclipse.draw2d.geometry.Point;
15	import org.eclipse.draw2d.geometry.PointList;	14	import org.eclipse.draw2d.geometry.PointList;
16	import org.eclipse.draw2d.geometry.Rectangle;	15	import org.eclipse.draw2d.geometry.Rectangle;
Lines 19-24 Link Here
19	* @author Randy Hudson	18	* @author Randy Hudson
20	*/	19	*/
21	class RouteEdges extends GraphVisitor {	20	class RouteEdges extends GraphVisitor {
		21
		22	private static int OBSTACLE_WIDTH = 10000;
22		23
23	/**	24	/**
24	* @see GraphVisitor#visit(DirectedGraph)	25	* @see GraphVisitor#visit(DirectedGraph)
Lines 38-82 Link Here
38	edge.getTargetOffset() + edge.target.x,	39	edge.getTargetOffset() + edge.target.x,
39	edge.target.y);	40	edge.target.y);
40		41
41	if (edge.vNodes != null)	42	if (edge.getRoutingStyle() == Edge.ORTHOGONAL_ROUTING_STYLE) {
42	routeLongEdge(edge, g);	43	routeOrthogonalEdge(edge, g);
43	else {	44	} else {
44	PointList list = new PointList();	45	routeEdge(edge, g);
45	list.addPoint(edge.start);
46	list.addPoint(edge.end);
47	edge.setPoints(list);
48	}	46	}
49	}	47	}
50	}	48	}
51		49
52	static void routeLongEdge(Edge edge, DirectedGraph g) {	50	void routeEdge(Edge edge, DirectedGraph g) {
53	ShortestPathRouter router = new ShortestPathRouter();	51	ShortestPathRouter router = new ShortestPathRouter();
54	Path path = new Path(edge.start, edge.end);	52	Path path = new Path(edge.start, edge.end);
55	router.addPath(path);	53	router.addPath(path);
56	Rectangle o;	54	if (edge.vNodes != null) {
57	Insets padding;	55	for (int i = 0; i < edge.vNodes.size(); i++) {
58	for (int i = 0; i < edge.vNodes.size(); i++) {	56	Node node = edge.vNodes.getNode(i);
59	VirtualNode node = (VirtualNode)edge.vNodes.get(i);	57	Rank r = g.ranks.getRank(node.rank);
60	Node neighbor;	58	if (node.left != null) {
61	if (node.left != null) {	59	int right = node.left.x + node.left.width + g.getPadding(node.left).right + edge.getPadding();
62	neighbor = node.left;	60	int width = Math.max(right, OBSTACLE_WIDTH);
63	o = new Rectangle(neighbor.x, neighbor.y, neighbor.width, neighbor.height);	61	int height = Math.max(r.height, 2);
64	padding = g.getPadding(neighbor);	62	router.addObstacle(new Rectangle(right - width, node.left.y, width, height));
65	o.width += padding.right + padding.left;	63	}
66	o.width += (edge.getPadding() * 2);	64	if (node.right != null) {
67	o.x -= (padding.left + edge.getPadding());	65	int left = node.right.x - g.getPadding(node.right).left - edge.getPadding();
68	o.union(o.getLocation().translate(-100000, 2));	66	int width = Math.max(g.size.width - left, OBSTACLE_WIDTH);
69	router.addObstacle(o);	67	int height = Math.max(r.height, 2);
70	}	68	router.addObstacle(new Rectangle(left, node.right.y, width, height));
71	if (node.right != null) {	69	}
72	neighbor = node.right;
73	o = new Rectangle(neighbor.x, neighbor.y, neighbor.width, neighbor.height);
74	padding = g.getPadding(neighbor);
75	o.width += padding.right + padding.left;
76	o.width += (edge.getPadding() * 2);
77	o.x -= (padding.left + edge.getPadding());
78	o.union(o.getLocation().translate(100000, 2));
79	router.addObstacle(o);
80	}	70	}
81	}	71	}
82	router.setSpacing(0);	72	router.setSpacing(0);
Lines 84-87 Link Here
84	edge.setPoints(path.getPoints());	74	edge.setPoints(path.getPoints());
85	}	75	}
86		76
		77	void routeOrthogonalEdge(Edge edge, DirectedGraph g) {
		78	PointList points = new PointList();
		79	points.addPoint(edge.start);
		80	Node previousNode = edge.source instanceof Subgraph ? ((Subgraph)edge.source).tail : edge.source;
		81	if (edge.vNodes != null) {
		82	for (int i = 0; i < edge.vNodes.size(); i++) {
		83	Node vNode = edge.vNodes.getNode(i);
		84	int nextPtX = vNode.x + vNode.width / 2;
		85	int prevPtX = points.getLastPoint().x;
		86	if (prevPtX != nextPtX) {
		87	Rank previousRank = g.ranks.getRank(previousNode.rank);
		88	int rankBottomY = previousRank.location + previousRank.height;
		89	int midY = rankBottomY + (vNode.y - rankBottomY) / 2;
		90	points.addPoint(prevPtX, midY);
		91	points.addPoint(nextPtX, midY);
		92	}
		93	previousNode = vNode;
		94	}
		95	}
		96	Point prevPt = points.getLastPoint();
		97	Point lastPt = edge.end;
		98	if (prevPt.x != lastPt.x) {
		99	Rank previousRank = g.ranks.getRank(previousNode.rank);
		100	int rankBottomY = previousRank.location + previousRank.height;
		101	int midY = rankBottomY + (lastPt.y - rankBottomY) / 2;
		102	points.addPoint(prevPt.x, midY);
		103	points.addPoint(lastPt.x, midY);
		104	}
		105	points.addPoint(edge.end);
		106	edge.setPoints(points);
		107	}
		108
87	}	109	}




/*******************************************************************************
 * Copyright (c) 2000, 2008 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at


import org.eclipse.draw2d.geometry.Dimension;
import org.eclipse.draw2d.geometry.Point;
import org.eclipse.draw2d.geometry.PrecisionPoint;

/**
 * RelativeBendpoint is a Bendpoint that calculates its location based on its distance

 * @since 2.0
 */
public Point getLocation() {
	PrecisionPoint a1 = new PrecisionPoint(getConnection().getSourceAnchor().getReferencePoint());
	PrecisionPoint a2 = new PrecisionPoint(getConnection().getTargetAnchor().getReferencePoint());
	
	getConnection().translateToRelative(a1);
	getConnection().translateToRelative(a2);
	
	return new PrecisionPoint((a1.preciseX() + d1.preciseWidth())
				* (1f - weight) + weight * (a2.preciseX() + d2.preciseWidth()),
				(a1.preciseY() + d1.preciseHeight()) * (1f - weight) + weight
						* (a2.preciseY() + d2.preciseHeight()));
	}
	getConnection().translateToRelative(p);
	return p;
}

/**
 * Sets the Connection this bendpoint should be associated with.




/*******************************************************************************
 * Copyright (c) 2005, 2008 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at

	 * Given the segments: u-------v. s-------t. If s->t is inside the triangle u-v-s, 
	 * then check whether the line u->u splits the line s->t.
	 */
	/* Values are casted to long to avoid integer overflows */
	long usX = (long) ux - sx;
	long usY = (long) uy - sy;
	long vsX = (long) vx - sx;
	long vsY = (long) vy - sy;
	long stX = (long) sx - tx;
	long stY = (long) sy - ty;
	if (productSign(cross(vsX, vsY, stX, stY), cross(stX, stY, usX, usY)) >= 0) {
		long vuX = (long) vx - ux;
		long vuY = (long) vy - uy;
		long utX = (long) ux - tx;
		long utY = (long) uy - ty;
		return productSign(cross(-usX, -usY, vuX, vuY), cross(vuX, vuY, utX, utY)) <= 0;
		boolean intersects = product <= 0;
		return intersects;
	}
	return false;
}

private static int productSign(long x, long y) {
	if (x == 0 || y == 0) {
		return 0;
	} else if (x < 0 ^ y < 0) {
		return -1;
	}
	return 1;
}

private static long cross(long x1, long y1, long x2, long y2) {
	return x1 * y2 - x2 * y1;
}


Lines 118-124 Link Here

(-)src/org/eclipse/draw2d/geometry/Point.java (-1 / +7 lines)
118	* @since 2.0	118	* @since 2.0
119	*/	119	*/
120	public double getDistance(Point pt) {	120	public double getDistance(Point pt) {
121	return Math.sqrt(getDistance2(pt));	121	return Math.sqrt(getPreciseDistance2(pt));
122	}	122	}
123		123
124	/**	124	/**
Lines 138-143 Link Here
138	return (int)result;	138	return (int)result;
139	}	139	}
140		140
		141	private double getPreciseDistance2(Point pt) {
		142	double i = pt.preciseX() - preciseX();
		143	double j = pt.preciseY() - preciseY();
		144	return i * i + j * j;
		145	}
		146
141	/**	147	/**
142	* Calculates the orthogonal distance to the specified point. The orthogonal distance is	148	* Calculates the orthogonal distance to the specified point. The orthogonal distance is
143	* the sum of the horizontal and vertical differences.	149	* the sum of the horizontal and vertical differences.

Lines 376-379 Link Here

(-)src/org/eclipse/draw2d/geometry/PrecisionRectangle.java (+9 lines)
376	return preciseHeight;	376	return preciseHeight;
377	}	377	}
378		378
		379	/**
		380	* @see org.eclipse.draw2d.geometry.Rectangle#setSize(org.eclipse.draw2d.geometry.Dimension)
		381	*/
		382	public Rectangle setSize(Dimension d) {
		383	preciseWidth = d.preciseWidth();
		384	preciseHeight = d.preciseHeight();
		385	return super.setSize(d);
		386	}
		387
379	}	388	}




/*******************************************************************************
 * Copyright (c) 2008 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/

package org.eclipse.draw2d.graph;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;

import org.eclipse.draw2d.geometry.Geometry;
import org.eclipse.draw2d.geometry.Point;

/**
 * Graph visitor in charge of spacing out edges such that they don't overlap.
 * Currently the graph visitor insures that outgoing edges don't overlap for nodes,
 * the height of which is different from the rank height.  
 * @since 3.4
 */
class SpaceOutEdges extends GraphVisitor {

	void revisit(DirectedGraph g) {
		for (int i = 0; i < g.nodes.size(); i++) {
			Node n = g.nodes.getNode(i);
			Rank rank = g.ranks.getRank(n.rank);
			if (!n.outgoing.isEmpty() && n.height != rank.height) {
				EdgeList leftEdges = new EdgeList();
				EdgeList rightEdges = new EdgeList();
				for (Iterator itr = n.outgoing.iterator(); itr.hasNext();) {
					Edge e = (Edge) itr.next();
					if (e.getRoutingStyle() == Edge.DEFAULT_ROUTING_STYLE) {
						/*
						 * Filtering of edges on left and right edges is done
						 * based on the default source end point. Hence, edge#offsetSource
						 * is ignored.
						 */
						int startX = n.x + n.outgoingOffset;
						int endX = e.getPoints().getPoint(1).x;
						if (endX > startX && n.right != null) {
							rightEdges.add(e);
						} else if (endX < startX && n.left != null) {
							leftEdges.add(e);
						}
					}
				}
				
				if (!leftEdges.isEmpty()) {
					Collections.sort(leftEdges, new EdgeComparator());
					int obstructionX;
					int initialObstructionX = obstructionX = n.left.x + n.left.width + g.getPadding(n.left).right;
					for (int j = 0; j < leftEdges.size(); j++) {
						Edge e = leftEdges.getEdge(j);
						Point first = e.getPoints().getFirstPoint();
						Point second = e.getPoints().getPoint(1);
						if (Geometry.linesIntersect(first.x, first.y, second.x, second.y, obstructionX, n.y, obstructionX, n.y + rank.height)) {
							e.getPoints().insertPoint(new Point(obstructionX, n.y + rank.height), 1);
							obstructionX += (first.x - initialObstructionX) / leftEdges.size(); 
						} else {
							/*
							 * If edge segment doesn't intersect the obstruction line then the rest of them
							 * won't intersect it either.
							 */
							break;
						}
					}
				}
				
				if (!rightEdges.isEmpty()) {
					Collections.sort(rightEdges, new EdgeComparator());
					int obstructionX;
					int initialObstructionX = obstructionX = n.right.x - g.getPadding(n.right).left;
					for (int j = rightEdges.size(); j > 0; j--) {
						Edge e = rightEdges.getEdge(j - 1);
						Point first = e.getPoints().getFirstPoint();
						Point second = e.getPoints().getPoint(1);
						if (Geometry.linesIntersect(first.x, first.y, second.x, second.y, obstructionX, n.y, obstructionX, n.y + rank.height)) {
							e.getPoints().insertPoint(new Point(obstructionX, n.y + rank.height), 1);
							obstructionX -= (initialObstructionX - first.x) / rightEdges.size(); 
						} else {
							/*
							 * If edge segment doesn't intersect the obstruction line then the rest of them
							 * won't intersect it either.
							 */
							break;
						}
					}		
				}	
				
			}
		}
	}
	
	/**
	 * Sorts edges in ascending order based on their direction (left-most to right-most)
	 * @since 3.4
	 */
	private class EdgeComparator implements Comparator {
		public int compare(Object arg0, Object arg1) {
			Edge e1 = (Edge) arg0;
			Edge e2 = (Edge) arg1;
			int x1 = e1.vNodes != null && !e1.vNodes.isEmpty() ? e1.vNodes.getNode(0).x : e1.getTargetOffset() + e1.target.x;
			int x2 = e2.vNodes != null && !e2.vNodes.isEmpty() ? e2.vNodes.getNode(0).x : e2.getTargetOffset() + e2.target.x;
			if (x1 == x2) {
				return 0;
			} else if (x1 > x2) {
				return 1;
			} else {
				return -1;
			}
		}	
	}
}




/*******************************************************************************
 * Copyright (c) 2005, 2008 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at


}

public static DirectedGraph fourLevelOrthogonalBinaryTree() {
	NodeList nodes = new NodeList();
	EdgeList edges = new EdgeList();
	
	Node row[], firstRow[];
	firstRow = new Node[2];
	firstRow[1] = new Node("root");
	addNodes(nodes, firstRow);
	
	row = joinRows(nodes, edges, firstRow, new int[] {1,1, 1, 2});
	
	row = joinRows(nodes, edges, row, new int[] {1,1,1,2,2,3,2,4});
	
	row = joinRows(nodes, edges, row, new int[] {1,1,1,2,2,3,2,4,3,5,3,6,4,7,4,8});
	
	for (int i = 0; i < edges.size(); i++) {
		edges.getEdge(i).setRoutingStyle(Edge.ORTHOGONAL_ROUTING_STYLE);
	}
		
	DirectedGraph graph = new DirectedGraph();
	graph.nodes = nodes;
	graph.edges = edges;
	
	new DirectedGraphLayout()
		.visit(graph);
	
	return graph;
}

public static DirectedGraph variousHeightNodesGraph_Test() {
	Node n1, n2, n3;
	Node n4, n5, n6, n7, n8, n9;
	NodeList nodes = new NodeList();
	EdgeList edges = new EdgeList();
	
	
	nodes.add(n1 = new Node("1"));
	nodes.add(n2 = new Node("2"));
	nodes.add(n3 = new Node("3"));
	nodes.add(n4 = new Node("4"));
	nodes.add(n5 = new Node("5"));
	nodes.add(n6 = new Node("6"));
	nodes.add(n7 = new Node("7"));
	nodes.add(n8 = new Node("8"));
	nodes.add(n9 = new Node("9"));
	
	n2.width = 200;
	n2.height = 350;
	
	edges.add(new Edge(n1, n4));
	edges.add(new Edge(n1, n5));
	edges.add(new Edge(n1, n6));
	edges.add(new Edge(n1, n7));
	edges.add(new Edge(n1, n8));
	edges.add(new Edge(n1, n9));
	
//	edges.add(new Edge(n2, n4));
//	edges.add(new Edge(n2, n5));
	edges.add(new Edge(n2, n6));
	edges.add(new Edge(n2, n7));
//	edges.add(new Edge(n2, n8));
//	edges.add(new Edge(n2, n9));

	edges.add(new Edge(n3, n4));
	edges.add(new Edge(n3, n5));
	edges.add(new Edge(n3, n6));
	edges.add(new Edge(n3, n7));
	edges.add(new Edge(n3, n8));
	edges.add(new Edge(n3, n9));
	
	DirectedGraph graph = new DirectedGraph();
	graph.nodes = nodes;
	graph.edges = edges;

	new DirectedGraphLayout()
		.visit(graph);
	return graph;	
}

}




/*******************************************************************************
 * Copyright (c) 2005, 2008 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at

}

public static CompoundDirectedGraph flowChart() {
	CompoundDirectedGraph graph = createFlowChartGraph();
	new CompoundDirectedGraphLayout()
		.visit(graph);
	return graph;
}

public static CompoundDirectedGraph flowChartOrthogonalEdges() {
	CompoundDirectedGraph graph = createFlowChartGraph();
	for (int i = 0; i < graph.edges.size(); i++) {
		graph.edges.getEdge(i).setRoutingStyle(Edge.ORTHOGONAL_ROUTING_STYLE);
	}
	new CompoundDirectedGraphLayout()
		.visit(graph);
	return graph;
}

private static CompoundDirectedGraph createFlowChartGraph() {
	NodeList nodes = new NodeList();
	EdgeList edges = new EdgeList();
	

	CompoundDirectedGraph graph = new CompoundDirectedGraph();
	graph.nodes = nodes;
	graph.edges = edges;
	
	new CompoundDirectedGraphLayout()
		.visit(graph);
	return graph;
}


	return graph;
}

public static CompoundDirectedGraph variousHeightNodesGraph() {
	Subgraph s, s1, s2;
	Node n1, n2, n3, n4, n5;
	Node n6, n7;
	NodeList nodes = new NodeList();
	EdgeList edges = new EdgeList();
	
	nodes.add(s = new Subgraph("diagram"));
	nodes.add(s1 = new Subgraph("subgraph 1", s));
	nodes.add(s2 = new Subgraph("subgraph 2", s));
	
	nodes.add(n1 = new Node("1", s1));
	nodes.add(n2 = new Node("2", s1));
	nodes.add(n3 = new Node("3", s1));
	nodes.add(n4 = new Node("4", s1));
	nodes.add(n5 = new Node("5", s1));
	nodes.add(n6 = new Node("6", s2));
	nodes.add(n7 = new Node("7", s2));
	
	n1.width = n4.width = n5.width = n6.width = n6.height = n7.width = n7.height = 50;
	n2.width = n3.width = 120;
	n1.height = n4.height = n5.height = 30;
	n2.height = n3.height = 400;
	
	edges.add(new Edge(n1, n5));
	edges.add(new Edge(n2, n5));
	edges.add(new Edge(n3, n5));
	edges.add(new Edge(n4, n5));
	edges.add(new Edge(n2, n7));
	edges.add(new Edge(n4, n6));
	edges.add(new Edge(s1, s2));
	
	CompoundDirectedGraph graph = new CompoundDirectedGraph();
	graph.nodes = nodes;
	graph.edges = edges;

	new CompoundDirectedGraphLayout()
		.visit(graph);
	return graph;	
}

}

Return to bug 221214

Lines 1-5 Link Here

(-)src/org/eclipse/draw2d/examples/graph/GraphTests.java (-1 / +80 lines)
1	/*******************************************************************************	1	/*******************************************************************************
2	* Copyright (c) 2005 IBM Corporation and others.	2	* Copyright (c) 2005, 2008 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials	3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0	4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at	5	* which accompanies this distribution, and is available at
Lines 779-782 Link Here
779		779
780	}	780	}
781		781
		782	public static DirectedGraph fourLevelOrthogonalBinaryTree() {
		783	NodeList nodes = new NodeList();
		784	EdgeList edges = new EdgeList();
		785
		786	Node row[], firstRow[];
		787	firstRow = new Node[2];
		788	firstRow[1] = new Node("root");
		789	addNodes(nodes, firstRow);
		790
		791	row = joinRows(nodes, edges, firstRow, new int[] {1,1, 1, 2});
		792
		793	row = joinRows(nodes, edges, row, new int[] {1,1,1,2,2,3,2,4});
		794
		795	row = joinRows(nodes, edges, row, new int[] {1,1,1,2,2,3,2,4,3,5,3,6,4,7,4,8});
		796
		797	for (int i = 0; i < edges.size(); i++) {
		798	edges.getEdge(i).setRoutingStyle(Edge.ORTHOGONAL_ROUTING_STYLE);
		799	}
		800
		801	DirectedGraph graph = new DirectedGraph();
		802	graph.nodes = nodes;
		803	graph.edges = edges;
		804
		805	new DirectedGraphLayout()
		806	.visit(graph);
		807
		808	return graph;
		809	}
		810
		811	public static DirectedGraph variousHeightNodesGraph_Test() {
		812	Node n1, n2, n3;
		813	Node n4, n5, n6, n7, n8, n9;
		814	NodeList nodes = new NodeList();
		815	EdgeList edges = new EdgeList();
		816
		817
		818	nodes.add(n1 = new Node("1"));
		819	nodes.add(n2 = new Node("2"));
		820	nodes.add(n3 = new Node("3"));
		821	nodes.add(n4 = new Node("4"));
		822	nodes.add(n5 = new Node("5"));
		823	nodes.add(n6 = new Node("6"));
		824	nodes.add(n7 = new Node("7"));
		825	nodes.add(n8 = new Node("8"));
		826	nodes.add(n9 = new Node("9"));
		827
		828	n2.width = 200;
		829	n2.height = 350;
		830
		831	edges.add(new Edge(n1, n4));
		832	edges.add(new Edge(n1, n5));
		833	edges.add(new Edge(n1, n6));
		834	edges.add(new Edge(n1, n7));
		835	edges.add(new Edge(n1, n8));
		836	edges.add(new Edge(n1, n9));
		837
		838	// edges.add(new Edge(n2, n4));
		839	// edges.add(new Edge(n2, n5));
		840	edges.add(new Edge(n2, n6));
		841	edges.add(new Edge(n2, n7));
		842	// edges.add(new Edge(n2, n8));
		843	// edges.add(new Edge(n2, n9));
		844
		845	edges.add(new Edge(n3, n4));
846	edges.add(new Edge(n3, n5));
847	edges.add(new Edge(n3, n6));
848	edges.add(new Edge(n3, n7));
849	edges.add(new Edge(n3, n8));
850	edges.add(new Edge(n3, n9));
851
852	DirectedGraph graph = new DirectedGraph();
853	graph.nodes = nodes;
854	graph.edges = edges;
855
856	new DirectedGraphLayout()
857	.visit(graph);
858	return graph;
859	}
860
782	}	861	}

Lines 1-5 Link Here

(-)src/org/eclipse/draw2d/examples/graph/CompoundGraphTests.java (-4 / +59 lines)
1	/*******************************************************************************	1	/*******************************************************************************
2	* Copyright (c) 2005, 2007 IBM Corporation and others.	2	* Copyright (c) 2005, 2008 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials	3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0	4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at	5	* which accompanies this distribution, and is available at
Lines 158-163 Link Here
158	}	158	}
159		159
160	public static CompoundDirectedGraph flowChart() {	160	public static CompoundDirectedGraph flowChart() {
		161	CompoundDirectedGraph graph = createFlowChartGraph();
		162	new CompoundDirectedGraphLayout()
		163	.visit(graph);
		164	return graph;
		165	}
		166
		167	public static CompoundDirectedGraph flowChartOrthogonalEdges() {
		168	CompoundDirectedGraph graph = createFlowChartGraph();
		169	for (int i = 0; i < graph.edges.size(); i++) {
		170	graph.edges.getEdge(i).setRoutingStyle(Edge.ORTHOGONAL_ROUTING_STYLE);
		171	}
		172	new CompoundDirectedGraphLayout()
		173	.visit(graph);
		174	return graph;
		175	}
		176
		177	private static CompoundDirectedGraph createFlowChartGraph() {
161	NodeList nodes = new NodeList();	178	NodeList nodes = new NodeList();
162	EdgeList edges = new EdgeList();	179	EdgeList edges = new EdgeList();
163		180
Lines 272-280 Link Here
272	CompoundDirectedGraph graph = new CompoundDirectedGraph();	289	CompoundDirectedGraph graph = new CompoundDirectedGraph();
273	graph.nodes = nodes;	290	graph.nodes = nodes;
274	graph.edges = edges;	291	graph.edges = edges;
275
276	new CompoundDirectedGraphLayout()
277	.visit(graph);
278	return graph;	292	return graph;
279	}	293	}
280		294
Lines 516-519 Link Here
516	return graph;	530	return graph;
517	}	531	}
518		532
		533	public static CompoundDirectedGraph variousHeightNodesGraph() {
		534	Subgraph s, s1, s2;
		535	Node n1, n2, n3, n4, n5;
		536	Node n6, n7;
		537	NodeList nodes = new NodeList();
		538	EdgeList edges = new EdgeList();
		539
		540	nodes.add(s = new Subgraph("diagram"));
		541	nodes.add(s1 = new Subgraph("subgraph 1", s));
		542	nodes.add(s2 = new Subgraph("subgraph 2", s));
		543
		544	nodes.add(n1 = new Node("1", s1));
		545	nodes.add(n2 = new Node("2", s1));
		546	nodes.add(n3 = new Node("3", s1));
		547	nodes.add(n4 = new Node("4", s1));
		548	nodes.add(n5 = new Node("5", s1));
		549	nodes.add(n6 = new Node("6", s2));
		550	nodes.add(n7 = new Node("7", s2));
		551
		552	n1.width = n4.width = n5.width = n6.width = n6.height = n7.width = n7.height = 50;
		553	n2.width = n3.width = 120;
		554	n1.height = n4.height = n5.height = 30;
		555	n2.height = n3.height = 400;
		556
		557	edges.add(new Edge(n1, n5));
		558	edges.add(new Edge(n2, n5));
		559	edges.add(new Edge(n3, n5));
		560	edges.add(new Edge(n4, n5));
		561	edges.add(new Edge(n2, n7));
		562	edges.add(new Edge(n4, n6));
		563	edges.add(new Edge(s1, s2));
		564
		565	CompoundDirectedGraph graph = new CompoundDirectedGraph();
		566	graph.nodes = nodes;
		567	graph.edges = edges;
		568
		569	new CompoundDirectedGraphLayout()
		570	.visit(graph);
		571	return graph;
		572	}
		573
519	}	574	}

Lines 1-5 Link Here

(-)src/org/eclipse/draw2d/RelativeBendpoint.java (-13 / +11 lines)
1	/*******************************************************************************	1	/*******************************************************************************
2	* Copyright (c) 2000, 2005 IBM Corporation and others.	2	* Copyright (c) 2000, 2008 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials	3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0	4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at	5	* which accompanies this distribution, and is available at
Lines 12-17 Link Here
12		12
13	import org.eclipse.draw2d.geometry.Dimension;	13	import org.eclipse.draw2d.geometry.Dimension;
14	import org.eclipse.draw2d.geometry.Point;	14	import org.eclipse.draw2d.geometry.Point;
		15	import org.eclipse.draw2d.geometry.PrecisionPoint;
15		16
16	/**	17	/**
17	* RelativeBendpoint is a Bendpoint that calculates its location based on its distance	18	* RelativeBendpoint is a Bendpoint that calculates its location based on its distance
Lines 58-77 Link Here
58	* @since 2.0	59	* @since 2.0
59	*/	60	*/
60	public Point getLocation() {	61	public Point getLocation() {
61	Point a1 = getConnection().getSourceAnchor().getReferencePoint();	62	PrecisionPoint a1 = new PrecisionPoint(getConnection().getSourceAnchor().getReferencePoint());
62	Point a2 = getConnection().getTargetAnchor().getReferencePoint();	63	PrecisionPoint a2 = new PrecisionPoint(getConnection().getTargetAnchor().getReferencePoint());
63		64
64	Point p = new Point();	65	getConnection().translateToRelative(a1);
65	Dimension dim1 = d1.getCopy(), dim2 = d2.getCopy();	66	getConnection().translateToRelative(a2);
66		67
67	getConnection().translateToAbsolute(dim1);	68	return new PrecisionPoint((a1.preciseX() + d1.preciseWidth())
68	getConnection().translateToAbsolute(dim2);	69	* (1f - weight) + weight * (a2.preciseX() + d2.preciseWidth()),
69		70	(a1.preciseY() + d1.preciseHeight()) * (1f - weight) + weight
70	p.x = (int)((a1.x + dim1.width) * (1f - weight) + weight * (a2.x + dim2.width));	71	* (a2.preciseY() + d2.preciseHeight()));
71	p.y = (int)((a1.y + dim1.height) * (1f - weight) + weight * (a2.y + dim2.height));	72	}
72	getConnection().translateToRelative(p);
73	return p;
74	}
75		73
76	/**	74	/**
77	* Sets the Connection this bendpoint should be associated with.	75	* Sets the Connection this bendpoint should be associated with.

Lines 1-5 Link Here

(-)src/org/eclipse/draw2d/geometry/Geometry.java (-17 / +24 lines)
1	/*******************************************************************************	1	/*******************************************************************************
2	* Copyright (c) 2005 IBM Corporation and others.	2	* Copyright (c) 2005, 2008 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials	3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0	4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at	5	* which accompanies this distribution, and is available at
Lines 41-66 Link Here
41	* Given the segments: u-------v. s-------t. If s->t is inside the triangle u-v-s,	41	* Given the segments: u-------v. s-------t. If s->t is inside the triangle u-v-s,
42	* then check whether the line u->u splits the line s->t.	42	* then check whether the line u->u splits the line s->t.
43	*/	43	*/
44	int usX = ux - sx;	44	/* Values are casted to long to avoid integer overflows */
45	int usY = uy - sy;	45	long usX = (long) ux - sx;
46	int vsX = vx - sx;	46	long usY = (long) uy - sy;
47	int vsY = vy - sy;	47	long vsX = (long) vx - sx;
48	int stX = sx - tx;	48	long vsY = (long) vy - sy;
49	int stY = sy - ty;	49	long stX = (long) sx - tx;
50	long product = cross(vsX, vsY, stX, stY) * cross(stX, stY, usX, usY);	50	long stY = (long) sy - ty;
51	if (product >= 0) {	51	if (productSign(cross(vsX, vsY, stX, stY), cross(stX, stY, usX, usY)) >= 0) {
52	int vuX = vx - ux;	52	long vuX = (long) vx - ux;
53	int vuY = vy - uy;	53	long vuY = (long) vy - uy;
54	int utX = ux - tx;	54	long utX = (long) ux - tx;
55	int utY = uy - ty;	55	long utY = (long) uy - ty;
56	product = cross(-usX, -usY, vuX, vuY) * cross(vuX, vuY, utX, utY);	56	return productSign(cross(-usX, -usY, vuX, vuY), cross(vuX, vuY, utX, utY)) <= 0;
57	boolean intersects = product <= 0;
58	return intersects;
59	}	57	}
60	return false;	58	return false;
61	}	59	}
62		60
63	private static long cross(int x1, int y1, int x2, int y2) {	61	private static int productSign(long x, long y) {
		62	if (x == 0 \|\| y == 0) {
		63	return 0;
		64	} else if (x < 0 ^ y < 0) {
		65	return -1;
		66	}
		67	return 1;
		68	}
		69
		70	private static long cross(long x1, long y1, long x2, long y2) {
64	return x1 * y2 - x2 * y1;	71	return x1 * y2 - x2 * y1;
65	}	72	}
66		73

Added Link Here

(-)src/org/eclipse/draw2d/graph/SpaceOutEdges.java (+119 lines)
1	/*******************************************************************************
2	* Copyright (c) 2008 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Eclipse Public License v1.0
5	* which accompanies this distribution, and is available at
6	* http://www.eclipse.org/legal/epl-v10.html
7	*
8	* Contributors:
9	* IBM Corporation - initial API and implementation
10	*******************************************************************************/
11
12	package org.eclipse.draw2d.graph;
13
14	import java.util.Collections;
15	import java.util.Comparator;
16	import java.util.Iterator;
17
18	import org.eclipse.draw2d.geometry.Geometry;
19	import org.eclipse.draw2d.geometry.Point;
20
21	/**
22	* Graph visitor in charge of spacing out edges such that they don't overlap.
23	* Currently the graph visitor insures that outgoing edges don't overlap for nodes,
24	* the height of which is different from the rank height.
25	* @since 3.4
26	*/
27	class SpaceOutEdges extends GraphVisitor {
28
29	void revisit(DirectedGraph g) {
30	for (int i = 0; i < g.nodes.size(); i++) {
31	Node n = g.nodes.getNode(i);
32	Rank rank = g.ranks.getRank(n.rank);
33	if (!n.outgoing.isEmpty() && n.height != rank.height) {
34	EdgeList leftEdges = new EdgeList();
35	EdgeList rightEdges = new EdgeList();
36	for (Iterator itr = n.outgoing.iterator(); itr.hasNext();) {
37	Edge e = (Edge) itr.next();
38	if (e.getRoutingStyle() == Edge.DEFAULT_ROUTING_STYLE) {
39	/*
40	* Filtering of edges on left and right edges is done
41	* based on the default source end point. Hence, edge#offsetSource
42	* is ignored.
43	*/
44	int startX = n.x + n.outgoingOffset;
45	int endX = e.getPoints().getPoint(1).x;
46	if (endX > startX && n.right != null) {
47	rightEdges.add(e);
48	} else if (endX < startX && n.left != null) {
49	leftEdges.add(e);
50	}
51	}
52	}
53
54	if (!leftEdges.isEmpty()) {
55	Collections.sort(leftEdges, new EdgeComparator());
56	int obstructionX;
57	int initialObstructionX = obstructionX = n.left.x + n.left.width + g.getPadding(n.left).right;
58	for (int j = 0; j < leftEdges.size(); j++) {
59	Edge e = leftEdges.getEdge(j);
60	Point first = e.getPoints().getFirstPoint();
61	Point second = e.getPoints().getPoint(1);
62	if (Geometry.linesIntersect(first.x, first.y, second.x, second.y, obstructionX, n.y, obstructionX, n.y + rank.height)) {
63	e.getPoints().insertPoint(new Point(obstructionX, n.y + rank.height), 1);
64	obstructionX += (first.x - initialObstructionX) / leftEdges.size();
65	} else {
66	/*
67	* If edge segment doesn't intersect the obstruction line then the rest of them
68	* won't intersect it either.
69	*/
70	break;
71	}
72	}
73	}
74
75	if (!rightEdges.isEmpty()) {
76	Collections.sort(rightEdges, new EdgeComparator());
77	int obstructionX;
78	int initialObstructionX = obstructionX = n.right.x - g.getPadding(n.right).left;
79	for (int j = rightEdges.size(); j > 0; j--) {
80	Edge e = rightEdges.getEdge(j - 1);
81	Point first = e.getPoints().getFirstPoint();
82	Point second = e.getPoints().getPoint(1);
83	if (Geometry.linesIntersect(first.x, first.y, second.x, second.y, obstructionX, n.y, obstructionX, n.y + rank.height)) {
84	e.getPoints().insertPoint(new Point(obstructionX, n.y + rank.height), 1);
85	obstructionX -= (initialObstructionX - first.x) / rightEdges.size();
86	} else {
87	/*
88	* If edge segment doesn't intersect the obstruction line then the rest of them
89	* won't intersect it either.
90	*/
91	break;
92	}
93	}
94	}
95
96	}
97	}
98	}
99
100	/**
101	* Sorts edges in ascending order based on their direction (left-most to right-most)
102	* @since 3.4
103	*/
104	private class EdgeComparator implements Comparator {
105	public int compare(Object arg0, Object arg1) {
106	Edge e1 = (Edge) arg0;
107	Edge e2 = (Edge) arg1;
108	int x1 = e1.vNodes != null && !e1.vNodes.isEmpty() ? e1.vNodes.getNode(0).x : e1.getTargetOffset() + e1.target.x;
109	int x2 = e2.vNodes != null && !e2.vNodes.isEmpty() ? e2.vNodes.getNode(0).x : e2.getTargetOffset() + e2.target.x;
110	if (x1 == x2) {
111	return 0;
112	} else if (x1 > x2) {
113	return 1;
114	} else {
115	return -1;
116	}
117	}
118	}
119	}