Mercurial > projects > dwt2
comparison org.eclipse.draw2d/src/org/eclipse/draw2d/graph/InitialRankSolver.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, 2005 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.InitialRankSolver; | |
14 | |
15 import java.lang.all; | |
16 import org.eclipse.draw2d.graph.GraphVisitor; | |
17 import org.eclipse.draw2d.graph.DirectedGraph; | |
18 import org.eclipse.draw2d.graph.NodeList; | |
19 import org.eclipse.draw2d.graph.Node; | |
20 import org.eclipse.draw2d.graph.EdgeList; | |
21 import org.eclipse.draw2d.graph.Edge; | |
22 | |
23 /** | |
24 * Assigns a valid rank assignment to all nodes based on their edges. The assignment is | |
25 * not optimal in that it does not provide the minimum global length of edge lengths. | |
26 * @author Randy Hudson | |
27 * @since 2.1.2 | |
28 */ | |
29 class InitialRankSolver : GraphVisitor { | |
30 | |
31 protected DirectedGraph graph; | |
32 protected EdgeList candidates; | |
33 protected NodeList members; | |
34 | |
35 public this(){ | |
36 candidates = new EdgeList(); | |
37 members = new NodeList(); | |
38 } | |
39 | |
40 public void visit(DirectedGraph graph) { | |
41 this.graph = graph; | |
42 graph.edges.resetFlags(false); | |
43 graph.nodes.resetFlags(); | |
44 solve(); | |
45 } | |
46 | |
47 protected void solve() { | |
48 if (graph.nodes.size() is 0) | |
49 return; | |
50 NodeList unranked = new NodeList(graph.nodes); | |
51 NodeList rankMe = new NodeList(); | |
52 Node node; | |
53 int i; | |
54 while (!unranked.isEmpty()) { | |
55 rankMe.clear(); | |
56 for (i = 0; i < unranked.size();) { | |
57 node = unranked.getNode(i); | |
58 if (node.incoming.isCompletelyFlagged()) { | |
59 rankMe.add(node); | |
60 unranked.remove(i); | |
61 } else | |
62 i++; | |
63 } | |
64 if (rankMe.size() is 0) | |
65 throw new RuntimeException("Cycle detected in graph"); //$NON-NLS-1$ | |
66 for (i = 0; i < rankMe.size(); i++) { | |
67 node = rankMe.getNode(i); | |
68 assignMinimumRank(node); | |
69 node.outgoing.setFlags(true); | |
70 } | |
71 } | |
72 | |
73 connectForest(); | |
74 } | |
75 | |
76 private void connectForest() { | |
77 List forest = new ArrayList(); | |
78 Stack stack = new Stack(); | |
79 NodeList tree; | |
80 graph.nodes.resetFlags(); | |
81 for (int i = 0; i < graph.nodes.size(); i++) { | |
82 Node neighbor, n = graph.nodes.getNode(i); | |
83 if (n.flag) | |
84 continue; | |
85 tree = new NodeList(); | |
86 stack.push(n); | |
87 while (!stack.isEmpty()) { | |
88 n = cast(Node) stack.pop(); | |
89 n.flag = true; | |
90 tree.add(n); | |
91 for (int s = 0; s < n.incoming.size(); s++) { | |
92 neighbor = n.incoming.getEdge(s).source; | |
93 if (!neighbor.flag) | |
94 stack.push(neighbor); | |
95 } | |
96 for (int s = 0; s < n.outgoing.size(); s++) { | |
97 neighbor = n.outgoing.getEdge(s).target; | |
98 if (!neighbor.flag) | |
99 stack.push(neighbor); | |
100 } | |
101 } | |
102 forest.add(tree); | |
103 } | |
104 | |
105 if (forest.size() > 1) { | |
106 //connect the forest | |
107 graph.forestRoot = new Node(stringcast("the forest root")); //$NON-NLS-1$ | |
108 graph.nodes.add(graph.forestRoot); | |
109 for (int i = 0; i < forest.size(); i++) { | |
110 tree = cast(NodeList) forest.get(i); | |
111 graph.edges.add(new Edge(graph.forestRoot, tree.getNode(0), 0, 0)); | |
112 } | |
113 } | |
114 } | |
115 | |
116 private void assignMinimumRank(Node node) { | |
117 int rank = 0; | |
118 Edge e; | |
119 for (int i1 = 0; i1 < node.incoming.size(); i1++) { | |
120 e = node.incoming.getEdge(i1); | |
121 rank = Math.max(rank, e.delta + e.source.rank); | |
122 } | |
123 node.rank = rank; | |
124 } | |
125 | |
126 } |