Mercurial > projects > dwt-addons

comparison dwtx/draw2d/graph/SortSubgraphs.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, 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 dwtx.draw2d.graph.SortSubgraphs;
14
15 import dwt.dwthelper.utils;
16 import dwtx.dwtxhelper.Collection;
17 import dwtx.draw2d.graph.GraphVisitor;
18 import dwtx.draw2d.graph.NestingTree;
19 import dwtx.draw2d.graph.CompoundDirectedGraph;
20 import dwtx.draw2d.graph.Node;
21 import dwtx.draw2d.graph.NodeList;
22 import dwtx.draw2d.graph.NodePair;
23 import dwtx.draw2d.graph.DirectedGraph;
24 import dwtx.draw2d.graph.RankList;
25 import dwtx.draw2d.graph.Rank;
26 import dwtx.draw2d.graph.Subgraph;
27
28 /**
29 * Performs a topological sort from left to right of the subgraphs in a compound directed
30 * graph. This ensures that subgraphs do not intertwine.
31 * @author Randy Hudson
32 * @since 2.1.2
33 */
34 class SortSubgraphs : GraphVisitor {
35
36 CompoundDirectedGraph g;
37
38 NestingTree[] nestingTrees;
39
40 Set orderingGraphEdges;
41 Set orderingGraphNodes;
42 NodePair pair;
43
44 public this(){
45 orderingGraphEdges = new HashSet();
46 orderingGraphNodes = new HashSet();
47 pair = new NodePair();
48 }
49
50 private void breakSubgraphCycles() {
51 //The stack of nodes which have no unmarked incoming edges
52 List noLefts = new ArrayList();
53
54 int index = 1;
55 //Identify all initial nodes for removal
56 for (Iterator iter = orderingGraphNodes.iterator(); iter.hasNext();) {
57 Node node = cast(Node)iter.next();
58 if (node.x is 0)
59 sortedInsert(noLefts, node);
60 }
61
62 Node cycleRoot;
63 do {
64 //Remove all leftmost nodes, updating the nodes to their right
65 while (noLefts.size() > 0) {
66 Node node = cast(Node)noLefts.remove(noLefts.size() - 1);
67 node.sortValue = index++;
68 orderingGraphNodes.remove(node);
69 // System.out.println("removed:" + node);
70 NodeList rightOf = rightOf(node);
71 if (rightOf is null)
72 continue;
73 for (int i = 0; i < rightOf.size(); i++) {
74 Node right = rightOf.getNode(i);
75 right.x--;
76 if (right.x is 0)
77 sortedInsert(noLefts, right);
78 }
79 }
80 cycleRoot = null;
81 double min = Double.MAX_VALUE;
82 for (Iterator iter = orderingGraphNodes.iterator(); iter.hasNext();) {
83 Node node = cast(Node)iter.next();
84 if (node.sortValue < min) {
85 cycleRoot = node;
86 min = node.sortValue;
87 }
88 }
89 if (cycleRoot !is null) {
90 //break the cycle;
91 sortedInsert(noLefts, cycleRoot);
92 // System.out.println("breaking cycle with:" + cycleRoot);
93 // Display.getCurrent().beep();
94 cycleRoot.x = -1; //prevent x from ever reaching 0
95 } // else if (OGmembers.size() > 0)
96 //System.out.println("FAILED TO FIND CYCLE ROOT"); //$NON-NLS-1$
97 } while (cycleRoot !is null);
98 }
99
100 private void buildSubgraphOrderingGraph() {
101 RankList ranks = g.ranks;
102 nestingTrees = new NestingTree[ranks.size()];
103 for (int r = 0; r < ranks.size(); r++) {
104 NestingTree entry = NestingTree.buildNestingTreeForRank(ranks.getRank(r));
105 nestingTrees[r] = entry;
106 entry.calculateSortValues();
107 entry.recursiveSort(false);
108 }
109
110 for (int i = 0; i < nestingTrees.length; i++) {
111 NestingTree entry = nestingTrees[i];
112 buildSubgraphOrderingGraph(entry);
113 }
114 }
115
116 private void buildSubgraphOrderingGraph(NestingTree entry) {
117 NodePair pair = new NodePair();
118 if (entry.isLeaf)
119 return;
120 for (int i = 0; i < entry.contents.size(); i++) {
121 Object right = entry.contents.get(i);
122 if (auto r = cast(Node)right )
123 pair.n2 = r;
124 else {
125 pair.n2 = (cast(NestingTree)right).subgraph;
126 buildSubgraphOrderingGraph(cast(NestingTree)right);
127 }
128 if (pair.n1 !is null && !orderingGraphEdges.contains(pair)) {
129 orderingGraphEdges.add(pair);
130 leftToRight(pair.n1, pair.n2);
131 orderingGraphNodes.add(pair.n1);
132 orderingGraphNodes.add(pair.n2);
133 pair.n2.x++; //Using x field to count predecessors.
134 pair = new NodePair(pair.n2, null);
135 } else {
136 pair.n1 = pair.n2;
137 }
138 }
139 }
140
141 /**
142 * Calculates the average position P for each node and subgraph. The average position is
143 * stored in the sortValue for each node or subgraph.
144 *
145 * Runs in approximately linear time with respect to the number of nodes, including
146 * virtual nodes.
147 */
148 private void calculateSortValues() {
149 RankList ranks = g.ranks;
150
151 g.subgraphs.resetSortValues();
152 g.subgraphs.resetIndices();
153
154 /*
155 * For subgraphs, the sum of all positions is kept, along with the number of
156 * contributions, which is tracked in the subgraph's index field.
157 */
158 for (int r = 0; r < ranks.size(); r++) {
159 Rank rank = ranks.getRank(r);
160 for (int j = 0; j < rank.count(); j++) {
161 Node node = rank.getNode(j);
162 node.sortValue = node.index;
163 Subgraph parent = node.getParent();
164 while (parent !is null) {
165 parent.sortValue += node.sortValue;
166 parent.index++;
167 parent = parent.getParent();
168 }
169 }
170 }
171
172 /*
173 * For each subgraph, divide the sum of the positions by the number of contributions,
174 * to give the average position.
175 */
176 for (int i = 0; i < g.subgraphs.size(); i++) {
177 Subgraph subgraph = cast(Subgraph)g.subgraphs.get(i);
178 subgraph.sortValue /= subgraph.index;
179 }
180 }
181
182 private void repopulateRanks() {
183 for (int i = 0; i < nestingTrees.length; i++) {
184 Rank rank = g.ranks.getRank(i);
185 rank.clear();
186 nestingTrees[i].repopulateRank(rank);
187 }
188 }
189
190 private NodeList rightOf(Node left) {
191 return cast(NodeList)left.workingData[0];
192 }
193
194 private void leftToRight(Node left, Node right) {
195 rightOf(left).add(right);
196 }
197
198 void sortedInsert(List list, Node node) {
199 int insert = 0;
200 while (insert < list.size()
201 && (cast(Node)list.get(insert)).sortValue > node.sortValue)
202 insert++;
203 list.add(insert, node);
204 }
205
206 private void topologicalSort() {
207 for (int i = 0; i < nestingTrees.length; i++) {
208 nestingTrees[i].getSortValueFromSubgraph();
209 nestingTrees[i].recursiveSort(false);
210 }
211 }
212
213 void init() {
214 for (int r = 0; r < g.ranks.size(); r++) {
215 Rank rank = g.ranks.getRank(r);
216 for (int i = 0; i < rank.count(); i++) {
217 Node n = cast(Node)rank.get(i);
218 n.workingData[0] = new NodeList();
219 }
220 }
221 for (int i = 0; i < g.subgraphs.size(); i++) {
222 Subgraph s = cast(Subgraph)g.subgraphs.get(i);
223 s.workingData[0] = new NodeList();
224 }
225 }
226
227 public void visit(DirectedGraph dg) {
228 g = cast(CompoundDirectedGraph)dg;
229
230 init();
231 buildSubgraphOrderingGraph();
232 calculateSortValues();
233 breakSubgraphCycles();
234 topologicalSort();
235 repopulateRanks();
236 }
237
238 }