Mercurial > projects > dwt-addons

comparison dwtx/draw2d/graph/BreakCycles.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.BreakCycles;
14
15 import dwt.dwthelper.utils;
16 import dwtx.dwtxhelper.Collection;
17 import dwtx.draw2d.graph.GraphVisitor;
18 import dwtx.draw2d.graph.NodeList;
19 import dwtx.draw2d.graph.DirectedGraph;
20 import dwtx.draw2d.graph.Node;
21 import dwtx.draw2d.graph.Edge;
22
23 /**
24 * This visitor eliminates cycles in the graph using a "greedy" heuristic. Nodes which
25 * are sources and sinks are marked and placed in a source and sink list, leaving only
26 * nodes involved in cycles. A remaining node with the highest (outgoing-incoming) edges
27 * score is then chosen greedily as if it were a source. The process is repeated until all
28 * nodes have been marked and placed in a list. The lists are then concatenated, and any
29 * edges which go backwards in this list will be inverted during the layout procedure.
30 *
31 * @author Daniel Lee
32 * @since 2.1.2
33 */
34 class BreakCycles : GraphVisitor {
35
36 // Used in identifying cycles and in cycle removal.
37 // Flag field indicates "presence". If true, the node has been removed from the list.
38 NodeList graphNodes;
39
40 public this(){
41 graphNodes = new NodeList();
42 }
43
44 private bool allNodesFlagged() {
45 for (int i = 0; i < graphNodes.size(); i++) {
46 if (graphNodes.getNode(i).flag is false)
47 return false;
48 }
49 return true;
50 }
51
52 private void breakCycles(DirectedGraph g) {
53 initializeDegrees(g);
54 greedyCycleRemove(g);
55 invertEdges(g);
56 }
57
58 /*
59 * Returns true if g contains cycles, false otherwise
60 */
61 private bool containsCycles(DirectedGraph g) {
62 List noLefts = new ArrayList();
63 //Identify all initial nodes for removal
64 for (int i = 0; i < graphNodes.size(); i++) {
65 Node node = graphNodes.getNode(i);
66 if (getIncomingCount(node) is 0)
67 sortedInsert(noLefts, node);
68 }
69
70 while (noLefts.size() > 0) {
71 Node node = cast(Node)noLefts.remove(noLefts.size() - 1);
72 node.flag = true;
73 for (int i = 0; i < node.outgoing.size(); i++) {
74 Node right = node.outgoing.getEdge(i).target;
75 setIncomingCount(right, getIncomingCount(right) - 1);
76 if (getIncomingCount(right) is 0)
77 sortedInsert(noLefts, right);
78 }
79 }
80
81 if (allNodesFlagged())
82 return false;
83 return true;
84 }
85
86 /*
87 * Returns the node in graphNodes with the largest
88 * (outgoing edge count - incoming edge count) value
89 */
90 private Node findNodeWithMaxDegree() {
91 int max = Integer.MIN_VALUE;
92 Node maxNode = null;
93
94 for (int i = 0; i < graphNodes.size(); i++) {
95 Node node = graphNodes.getNode(i);
96 if (getDegree(node) >= max && node.flag is false) {
97 max = getDegree(node);
98 maxNode = node;
99 }
100 }
101 return maxNode;
102 }
103
104 private int getDegree(Node n) {
105 return n.workingInts[3];
106 }
107
108 private int getIncomingCount(Node n) {
109 return n.workingInts[0];
110 }
111
112 private int getInDegree(Node n) {
113 return n.workingInts[1];
114 }
115
116 private int getOrderIndex(Node n) {
117 return n.workingInts[0];
118 }
119
120 private int getOutDegree(Node n) {
121 return n.workingInts[2];
122 }
123
124 private void greedyCycleRemove(DirectedGraph g) {
125 NodeList sL = new NodeList();
126 NodeList sR = new NodeList();
127
128 do {
129 // Add all sinks and isolated nodes to sR
130 bool hasSink;
131 do {
132 hasSink = false;
133 for (int i = 0; i < graphNodes.size(); i++) {
134 Node node = graphNodes.getNode(i);
135 if (getOutDegree(node) is 0 && node.flag is false) {
136 hasSink = true;
137 node.flag = true;
138 updateIncoming(node);
139 sR.add(node);
140 break;
141 }
142 }
143 } while (hasSink);
144
145 // Add all sources to sL
146 bool hasSource;
147 do {
148 hasSource = false;
149 for (int i = 0; i < graphNodes.size(); i++) {
150 Node node = graphNodes.getNode(i);
151 if (getInDegree(node) is 0 && node.flag is false) {
152 hasSource = true;
153 node.flag = true;
154 updateOutgoing(node);
155 sL.add(node);
156 break;
157 }
158 }
159 } while (hasSource);
160
161 // When all sinks and sources are removed, choose a node with the
162 // maximum degree (outDegree - inDegree) and add it to sL
163 Node max = findNodeWithMaxDegree();
164 if (max !is null) {
165 sL.add(max);
166 max.flag = true;
167 updateIncoming(max);
168 updateOutgoing(max);
169 }
170 } while (!allNodesFlagged());
171
172 // Assign order indexes
173 int orderIndex = 0;
174 for (int i = 0; i < sL.size(); i++) {
175 setOrderIndex(sL.getNode(i), orderIndex++);
176 }
177 for (int i = sR.size() - 1; i >= 0; i--) {
178 setOrderIndex(sR.getNode(i), orderIndex++);
179 }
180 }
181
182 private void initializeDegrees(DirectedGraph g) {
183 graphNodes.resetFlags();
184 for (int i = 0; i < g.nodes.size(); i++) {
185 Node n = graphNodes.getNode(i);
186 setInDegree(n, n.incoming.size());
187 setOutDegree(n, n.outgoing.size());
188 setDegree(n, n.outgoing.size() - n.incoming.size());
189 }
190 }
191
192 private void invertEdges(DirectedGraph g) {
193 for (int i = 0; i < g.edges.size(); i++) {
194 Edge e = g.edges.getEdge(i);
195 if (getOrderIndex(e.source) > getOrderIndex(e.target)) {
196 e.invert();
197 e.isFeedback_ = true;
198 }
199 }
200 }
201
202 private void setDegree(Node n, int deg) {
203 n.workingInts[3] = deg;
204 }
205
206 private void setIncomingCount(Node n, int count) {
207 n.workingInts[0] = count;
208 }
209
210 private void setInDegree(Node n, int deg) {
211 n.workingInts[1] = deg;
212 }
213
214 private void setOutDegree(Node n, int deg) {
215 n.workingInts[2] = deg;
216 }
217
218 private void setOrderIndex(Node n, int index) {
219 n.workingInts[0] = index;
220 }
221
222 private void sortedInsert(List list, Node node) {
223 int insert = 0;
224 while (insert < list.size()
225 && (cast(Node)list.get(insert)).sortValue > node.sortValue)
226 insert++;
227 list.add(insert, node);
228 }
229
230 /*
231 * Called after removal of n. Updates the degree values of n's incoming nodes.
232 */
233 private void updateIncoming(Node n) {
234 for (int i = 0; i < n.incoming.size(); i++) {
235 Node in_ = n.incoming.getEdge(i).source;
236 if (in_.flag is false) {
237 setOutDegree(in_, getOutDegree(in_) - 1);
238 setDegree(in_, getOutDegree(in_) - getInDegree(in_));
239 }
240 }
241 }
242
243 /*
244 * Called after removal of n. Updates the degree values of n's outgoing nodes.
245 */
246 private void updateOutgoing(Node n) {
247 for (int i = 0; i < n.outgoing.size(); i++) {
248 Node out_ = n.outgoing.getEdge(i).target;
249 if (out_.flag is false) {
250 setInDegree(out_, getInDegree(out_) - 1);
251 setDegree(out_, getOutDegree(out_) - getInDegree(out_));
252 }
253 }
254 }
255
256 public void revisit(DirectedGraph g) {
257 for (int i = 0; i < g.edges.size(); i++) {
258 Edge e = g.edges.getEdge(i);
259 if (e.isFeedback())
260 e.invert();
261 }
262 }
263
264 /**
265 * @see GraphVisitor#visit(dwtx.draw2d.graph.DirectedGraph)
266 */
267 public void visit(DirectedGraph g) {
268 // put all nodes in list, initialize index
269 graphNodes.resetFlags();
270 for (int i = 0; i < g.nodes.size(); i++) {
271 Node n = g.nodes.getNode(i);
272 setIncomingCount(n, n.incoming.size());
273 graphNodes.add(n);
274 }
275 if (containsCycles(g)) {
276 breakCycles(g);
277 }
278 }
279
280 }