Mercurial > projects > dwt-addons

comparison dwtx/draw2d/graph/DirectedGraphLayout.d @ 98:95307ad235d9

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