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.Iterator;
|
14
|
|
15
|
/**
|
16
|
* Places nodes into ranks for a compound directed graph. If a subgraph spans a
|
17
|
* rank without any nodes which belong to that rank, a bridge node is inserted
|
18
|
* to prevent nodes from violating the subgraph boundary.
|
19
|
*
|
20
|
* @author Randy Hudson
|
21
|
* @since 2.1.2
|
22
|
*/
|
23
|
class CompoundPopulateRanks extends PopulateRanks {
|
24
|
|
25
|
public void visit(DirectedGraph g) {
|
26
|
CompoundDirectedGraph graph = (CompoundDirectedGraph) g;
|
27
|
|
28
|
/**
|
29
|
* Remove long containment edges at this point so they don't affect
|
30
|
* MinCross.
|
31
|
*/
|
32
|
Iterator containment = graph.containment.iterator();
|
33
|
while (containment.hasNext()) {
|
34
|
Edge e = (Edge) containment.next();
|
35
|
if (e.getSlack() > 0) {
|
36
|
graph.removeEdge(e);
|
37
|
containment.remove();
|
38
|
}
|
39
|
}
|
40
|
|
41
|
super.visit(g);
|
42
|
NodeList subgraphs = graph.subgraphs;
|
43
|
for (int i = 0; i < subgraphs.size(); i++) {
|
44
|
Subgraph subgraph = (Subgraph) subgraphs.get(i);
|
45
|
bridgeSubgraph(subgraph, graph);
|
46
|
}
|
47
|
}
|
48
|
|
49
|
/**
|
50
|
* @param subgraph
|
51
|
*/
|
52
|
private void bridgeSubgraph(Subgraph subgraph, CompoundDirectedGraph g) {
|
53
|
int offset = subgraph.head.rank;
|
54
|
boolean occupied[] = new boolean[subgraph.tail.rank
|
55
|
- subgraph.head.rank + 1];
|
56
|
Node bridge[] = new Node[occupied.length];
|
57
|
|
58
|
for (int i = 0; i < subgraph.members.size(); i++) {
|
59
|
Node n = (Node) subgraph.members.get(i);
|
60
|
if (n instanceof Subgraph) {
|
61
|
Subgraph s = (Subgraph) n;
|
62
|
for (int r = s.head.rank; r <= s.tail.rank; r++)
|
63
|
occupied[r - offset] = true;
|
64
|
} else
|
65
|
occupied[n.rank - offset] = true;
|
66
|
}
|
67
|
|
68
|
for (int i = 0; i < bridge.length; i++) {
|
69
|
if (!occupied[i]) {
|
70
|
Node br = bridge[i] = new Node("bridge", subgraph); //$NON-NLS-1$
|
71
|
br.rank = i + offset;
|
72
|
br.height = br.width = 0;
|
73
|
br.nestingIndex = subgraph.nestingIndex;
|
74
|
g.ranks.getRank(br.rank).add(br);
|
75
|
g.nodes.add(br);
|
76
|
}
|
77
|
}
|
78
|
}
|
79
|
|
80
|
}
|