Mercurial > projects > dwt2

annotate org.eclipse.draw2d/src/org/eclipse/draw2d/graph/DirectedGraphLayout.d @ 12:bc29606a740c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added dwt-addons in original directory structure of eclipse.org
author Frank Benoit <benoit@tionex.de>
date Sat, 14 Mar 2009 18:23:29 +0100
parents
children dbfb303e8fb0
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
12
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
1 /*******************************************************************************
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
2 * Copyright (c) 2003, 2007 IBM Corporation and others.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
3 * All rights reserved. This program and the accompanying materials
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
4 * are made available under the terms of the Eclipse Public License v1.0
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
5 * which accompanies this distribution, and is available at
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
6 * http://www.eclipse.org/legal/epl-v10.html
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
7 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
8 * Contributors:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
9 * IBM Corporation - initial API and implementation
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
10 * Port to the D programming language:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
11 * Frank Benoit <benoit@tionex.de>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
12 *******************************************************************************/
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
13 module org.eclipse.draw2d.graph.DirectedGraphLayout;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
14
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
15 import java.lang.all;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
16 import org.eclipse.draw2d.graph.TransposeMetrics;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
17 import org.eclipse.draw2d.graph.BreakCycles;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
18 import org.eclipse.draw2d.graph.RouteEdges;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
19 import org.eclipse.draw2d.graph.InitialRankSolver;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
20 import org.eclipse.draw2d.graph.TightSpanningTreeSolver;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
21 import org.eclipse.draw2d.graph.RankAssignmentSolver;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
22 import org.eclipse.draw2d.graph.PopulateRanks;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
23 import org.eclipse.draw2d.graph.VerticalPlacement;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
24 import org.eclipse.draw2d.graph.MinCross;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
25 import org.eclipse.draw2d.graph.LocalOptimizer;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
26 import org.eclipse.draw2d.graph.HorizontalPlacement;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
27 import org.eclipse.draw2d.graph.DirectedGraph;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
28 import org.eclipse.draw2d.graph.GraphVisitor;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
29
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
30 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
31 * Performs a graph layout of a <code>DirectedGraph</code>. The directed graph must meet
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
32 * the following conditions:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
33 * <UL>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
34 * <LI>The graph must be connected.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
35 * <LI>All edge's must be added to the graph's {@link DirectedGraph#edges edges} list
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
36 * exactly once.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
37 * <LI>All nodes must be added to the graph's {@link DirectedGraph#nodes nodes} list
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
38 * exactly once.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
39 * </UL>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
40 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
41 * This algorithm will:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
42 * <UL>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
43 * <LI>break cycles by inverting a set of feedback edges. Feedback edges will have the
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
44 * flag {@link Edge#isFeedback} set to <code>true</code>. The following statements are
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
45 * true with respect to the inverted edge. When the algorithm completes, it will invert
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
46 * the edges again, but will leave the feedback flags set.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
47 * <LI>for each node <em>n</em>, assign n to a "rank" R(n), such that: for each edge (m,
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
48 * n) in n.incoming, R(m)<=R(n)-(m,n).delta. The total weighted edge lengths shall be
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
49 * no greater than is necessary to meet this requirement for all edges in the graph.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
50 * <LI>attempt to order the nodes in their ranks as to minimize crossings.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
51 * <LI>assign <em>y</em> coordinates to each node based on its rank. The spacing
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
52 * between ranks is the sum of the bottom padding of the previous rank, and the top
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
53 * padding of the next rank.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
54 * <LI>assign <em>x</em> coordinates such that the graph is easily readable. The exact
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
55 * behavior is undefined, but will favor edge's with higher {@link Edge#weight}s. The
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
56 * minimum x value assigned to a node or bendpoint will be 0.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
57 * <LI>assign <em>bendpoints</em> to all edge's which span more than 1 rank.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
58 * </UL>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
59 * <P>For each NODE:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
60 * <UL>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
61 * <LI>The x coordinate will be assigned a value >= 0
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
62 * <LI>The y coordinate will be assigned a value >= 0
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
63 * <LI>The rank will be assigned a value >=0
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
64 * <LI>The height will be set to the height of the tallest node on the same row
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
65 * </UL>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
66 * <P>For each EDGE:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
67 * <UL>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
68 * <LI>If an edge spans more than 1 row, it will have a list of {@link
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
69 * org.eclipse.draw2d.graph.Edge#vNodes virtual} nodes. The virtual nodes will be
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
70 * assigned an x coordinate indicating the routing path for that edge.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
71 * <LI>If an edge is a feedback edge, it's <code>isFeedback</code> flag will be set,
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
72 * and if it has virtual nodes, they will be in reverse order (bottom-up).
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
73 * </UL>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
74 * <P>This class is not guaranteed to produce the same results for each invocation.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
75 * @author Randy Hudson
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
76 * @since 2.1.2
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
77 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
78 public class DirectedGraphLayout {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
79
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
80 List steps;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
81
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
82 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
83 * @since 3.1
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
84 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
85 public this() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
86 steps = new ArrayList();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
87 init();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
88 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
89
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
90 void init() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
91 steps.add(new TransposeMetrics());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
92 steps.add(new BreakCycles());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
93 steps.add(new RouteEdges());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
94 steps.add(new InitialRankSolver());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
95 steps.add(new TightSpanningTreeSolver());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
96 steps.add(new RankAssignmentSolver());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
97 steps.add(new PopulateRanks());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
98 steps.add(new VerticalPlacement());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
99 steps.add(new MinCross());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
100 steps.add(new LocalOptimizer());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
101 steps.add(new HorizontalPlacement());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
102 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
103
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
104 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
105 * Lays out the given graph
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
106 * @param graph the graph to layout
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
107 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
108 public void visit(DirectedGraph graph) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
109 if (graph.nodes.isEmpty())
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
110 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
111 for (int i = 0; i < steps.size(); i++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
112 GraphVisitor visitor = cast(GraphVisitor)steps.get(i);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
113 visitor.visit(graph);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
114 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
115 for (int i = steps.size() - 1; i >= 0; i--) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
116 GraphVisitor visitor = cast(GraphVisitor)steps.get(i);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
117 visitor.revisit(graph);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
118 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
119 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
120
bc29606a740c Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
121 }