Mercurial > projects > dwt2
comparison org.eclipse.draw2d/src/org/eclipse/draw2d/graph/DirectedGraphLayout.d @ 12:bc29606a740c
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 |
comparison
equal
deleted
inserted
replaced
11:43904fec5dca | 12:bc29606a740c |
---|---|
1 /******************************************************************************* | |
2 * Copyright (c) 2003, 2007 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 * Port to the D programming language: | |
11 * Frank Benoit <benoit@tionex.de> | |
12 *******************************************************************************/ | |
13 module org.eclipse.draw2d.graph.DirectedGraphLayout; | |
14 | |
15 import java.lang.all; | |
16 import org.eclipse.draw2d.graph.TransposeMetrics; | |
17 import org.eclipse.draw2d.graph.BreakCycles; | |
18 import org.eclipse.draw2d.graph.RouteEdges; | |
19 import org.eclipse.draw2d.graph.InitialRankSolver; | |
20 import org.eclipse.draw2d.graph.TightSpanningTreeSolver; | |
21 import org.eclipse.draw2d.graph.RankAssignmentSolver; | |
22 import org.eclipse.draw2d.graph.PopulateRanks; | |
23 import org.eclipse.draw2d.graph.VerticalPlacement; | |
24 import org.eclipse.draw2d.graph.MinCross; | |
25 import org.eclipse.draw2d.graph.LocalOptimizer; | |
26 import org.eclipse.draw2d.graph.HorizontalPlacement; | |
27 import org.eclipse.draw2d.graph.DirectedGraph; | |
28 import org.eclipse.draw2d.graph.GraphVisitor; | |
29 | |
30 /** | |
31 * Performs a graph layout of a <code>DirectedGraph</code>. The directed graph must meet | |
32 * the following conditions: | |
33 * <UL> | |
34 * <LI>The graph must be connected. | |
35 * <LI>All edge's must be added to the graph's {@link DirectedGraph#edges edges} list | |
36 * exactly once. | |
37 * <LI>All nodes must be added to the graph's {@link DirectedGraph#nodes nodes} list | |
38 * exactly once. | |
39 * </UL> | |
40 * | |
41 * This algorithm will: | |
42 * <UL> | |
43 * <LI>break cycles by inverting a set of feedback edges. Feedback edges will have the | |
44 * flag {@link Edge#isFeedback} set to <code>true</code>. The following statements are | |
45 * true with respect to the inverted edge. When the algorithm completes, it will invert | |
46 * the edges again, but will leave the feedback flags set. | |
47 * <LI>for each node <em>n</em>, assign n to a "rank" R(n), such that: for each edge (m, | |
48 * n) in n.incoming, R(m)<=R(n)-(m,n).delta. The total weighted edge lengths shall be | |
49 * no greater than is necessary to meet this requirement for all edges in the graph. | |
50 * <LI>attempt to order the nodes in their ranks as to minimize crossings. | |
51 * <LI>assign <em>y</em> coordinates to each node based on its rank. The spacing | |
52 * between ranks is the sum of the bottom padding of the previous rank, and the top | |
53 * padding of the next rank. | |
54 * <LI>assign <em>x</em> coordinates such that the graph is easily readable. The exact | |
55 * behavior is undefined, but will favor edge's with higher {@link Edge#weight}s. The | |
56 * minimum x value assigned to a node or bendpoint will be 0. | |
57 * <LI>assign <em>bendpoints</em> to all edge's which span more than 1 rank. | |
58 * </UL> | |
59 * <P>For each NODE: | |
60 * <UL> | |
61 * <LI>The x coordinate will be assigned a value >= 0 | |
62 * <LI>The y coordinate will be assigned a value >= 0 | |
63 * <LI>The rank will be assigned a value >=0 | |
64 * <LI>The height will be set to the height of the tallest node on the same row | |
65 * </UL> | |
66 * <P>For each EDGE: | |
67 * <UL> | |
68 * <LI>If an edge spans more than 1 row, it will have a list of {@link | |
69 * org.eclipse.draw2d.graph.Edge#vNodes virtual} nodes. The virtual nodes will be | |
70 * assigned an x coordinate indicating the routing path for that edge. | |
71 * <LI>If an edge is a feedback edge, it's <code>isFeedback</code> flag will be set, | |
72 * and if it has virtual nodes, they will be in reverse order (bottom-up). | |
73 * </UL> | |
74 * <P>This class is not guaranteed to produce the same results for each invocation. | |
75 * @author Randy Hudson | |
76 * @since 2.1.2 | |
77 */ | |
78 public class DirectedGraphLayout { | |
79 | |
80 List steps; | |
81 | |
82 /** | |
83 * @since 3.1 | |
84 */ | |
85 public this() { | |
86 steps = new ArrayList(); | |
87 init(); | |
88 } | |
89 | |
90 void init() { | |
91 steps.add(new TransposeMetrics()); | |
92 steps.add(new BreakCycles()); | |
93 steps.add(new RouteEdges()); | |
94 steps.add(new InitialRankSolver()); | |
95 steps.add(new TightSpanningTreeSolver()); | |
96 steps.add(new RankAssignmentSolver()); | |
97 steps.add(new PopulateRanks()); | |
98 steps.add(new VerticalPlacement()); | |
99 steps.add(new MinCross()); | |
100 steps.add(new LocalOptimizer()); | |
101 steps.add(new HorizontalPlacement()); | |
102 } | |
103 | |
104 /** | |
105 * Lays out the given graph | |
106 * @param graph the graph to layout | |
107 */ | |
108 public void visit(DirectedGraph graph) { | |
109 if (graph.nodes.isEmpty()) | |
110 return; | |
111 for (int i = 0; i < steps.size(); i++) { | |
112 GraphVisitor visitor = cast(GraphVisitor)steps.get(i); | |
113 visitor.visit(graph); | |
114 } | |
115 for (int i = steps.size() - 1; i >= 0; i--) { | |
116 GraphVisitor visitor = cast(GraphVisitor)steps.get(i); | |
117 visitor.revisit(graph); | |
118 } | |
119 } | |
120 | |
121 } |