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