|
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
|
/**
|
|
14
|
* Some utility methods for graphs.
|
|
15
|
*
|
|
16
|
* @author Eric Bordeau
|
|
17
|
* @since 2.1.2
|
|
18
|
*/
|
|
19
|
class GraphUtilities {
|
|
20
|
|
|
21
|
static Subgraph getCommonAncestor(Node left, Node right) {
|
|
22
|
Subgraph parent;
|
|
23
|
if (right instanceof Subgraph)
|
|
24
|
parent = (Subgraph) right;
|
|
25
|
else
|
|
26
|
parent = right.getParent();
|
|
27
|
while (parent != null) {
|
|
28
|
if (parent.isNested(left))
|
|
29
|
return parent;
|
|
30
|
parent = parent.getParent();
|
|
31
|
}
|
|
32
|
return null;
|
|
33
|
}
|
|
34
|
|
|
35
|
/**
|
|
36
|
* Returns <code>true</code> if the given graph contains at least one cycle.
|
|
37
|
*
|
|
38
|
* @param graph
|
|
39
|
* the graph to test
|
|
40
|
* @return whether the graph is cyclic
|
|
41
|
*/
|
|
42
|
public static boolean isCyclic(DirectedGraph graph) {
|
|
43
|
return isCyclic(new NodeList(graph.nodes));
|
|
44
|
}
|
|
45
|
|
|
46
|
/**
|
|
47
|
* Recursively removes leaf nodes from the list until there are no nodes
|
|
48
|
* remaining (acyclic) or there are no leaf nodes but the list is not empty
|
|
49
|
* (cyclic), then returns the result.
|
|
50
|
*
|
|
51
|
* @param nodes
|
|
52
|
* the list of nodes to test
|
|
53
|
* @return whether the graph is cyclic
|
|
54
|
*/
|
|
55
|
public static boolean isCyclic(NodeList nodes) {
|
|
56
|
if (nodes.isEmpty())
|
|
57
|
return false;
|
|
58
|
int size = nodes.size();
|
|
59
|
// remove all the leaf nodes from the graph
|
|
60
|
for (int i = 0; i < nodes.size(); i++) {
|
|
61
|
Node node = nodes.getNode(i);
|
|
62
|
if (node.outgoing == null || node.outgoing.isEmpty()) { // this is a
|
|
63
|
// leaf node
|
|
64
|
nodes.remove(node);
|
|
65
|
for (int j = 0; j < node.incoming.size(); j++) {
|
|
66
|
Edge e = node.incoming.getEdge(j);
|
|
67
|
e.source.outgoing.remove(e);
|
|
68
|
}
|
|
69
|
}
|
|
70
|
}
|
|
71
|
// if no nodes were removed, that means there are no leaf nodes and the
|
|
72
|
// graph is cyclic
|
|
73
|
if (nodes.size() == size)
|
|
74
|
return true;
|
|
75
|
// leaf nodes were removed, so recursively call this method with the new
|
|
76
|
// list
|
|
77
|
return isCyclic(nodes);
|
|
78
|
}
|
|
79
|
|
|
80
|
/**
|
|
81
|
* Counts the number of edge crossings in a DirectedGraph
|
|
82
|
*
|
|
83
|
* @param graph
|
|
84
|
* the graph whose crossed edges are counted
|
|
85
|
* @return the number of edge crossings in the graph
|
|
86
|
*/
|
|
87
|
public static int numberOfCrossingsInGraph(DirectedGraph graph) {
|
|
88
|
int crossings = 0;
|
|
89
|
for (int i = 0; i < graph.ranks.size(); i++) {
|
|
90
|
Rank rank = graph.ranks.getRank(i);
|
|
91
|
crossings += numberOfCrossingsInRank(rank);
|
|
92
|
}
|
|
93
|
return crossings;
|
|
94
|
}
|
|
95
|
|
|
96
|
/**
|
|
97
|
* Counts the number of edge crossings in a Rank
|
|
98
|
*
|
|
99
|
* @param rank
|
|
100
|
* the rank whose crossed edges are counted
|
|
101
|
* @return the number of edge crossings in the rank
|
|
102
|
*/
|
|
103
|
public static int numberOfCrossingsInRank(Rank rank) {
|
|
104
|
int crossings = 0;
|
|
105
|
for (int i = 0; i < rank.size() - 1; i++) {
|
|
106
|
Node currentNode = rank.getNode(i);
|
|
107
|
Node nextNode;
|
|
108
|
for (int j = i + 1; j < rank.size(); j++) {
|
|
109
|
nextNode = rank.getNode(j);
|
|
110
|
EdgeList currentOutgoing = currentNode.outgoing;
|
|
111
|
EdgeList nextOutgoing = nextNode.outgoing;
|
|
112
|
for (int k = 0; k < currentOutgoing.size(); k++) {
|
|
113
|
Edge currentEdge = currentOutgoing.getEdge(k);
|
|
114
|
for (int l = 0; l < nextOutgoing.size(); l++) {
|
|
115
|
if (nextOutgoing.getEdge(l).getIndexForRank(
|
|
116
|
currentNode.rank + 1) < currentEdge
|
|
117
|
.getIndexForRank(currentNode.rank + 1))
|
|
118
|
crossings++;
|
|
119
|
}
|
|
120
|
}
|
|
121
|
}
|
|
122
|
}
|
|
123
|
return crossings;
|
|
124
|
}
|
|
125
|
|
|
126
|
private static NodeList search(Node node, NodeList list) {
|
|
127
|
if (node.flag)
|
|
128
|
return list;
|
|
129
|
node.flag = true;
|
|
130
|
list.add(node);
|
|
131
|
for (int i = 0; i < node.outgoing.size(); i++)
|
|
132
|
search(node.outgoing.getEdge(i).target, list);
|
|
133
|
return list;
|
|
134
|
}
|
|
135
|
|
|
136
|
/**
|
|
137
|
* Returns <code>true</code> if adding an edge between the 2 given nodes
|
|
138
|
* will introduce a cycle in the containing graph.
|
|
139
|
*
|
|
140
|
* @param source
|
|
141
|
* the potential source node
|
|
142
|
* @param target
|
|
143
|
* the potential target node
|
|
144
|
* @return whether an edge between the 2 given nodes will introduce a cycle
|
|
145
|
*/
|
|
146
|
public static boolean willCauseCycle(Node source, Node target) {
|
|
147
|
NodeList nodes = search(target, new NodeList());
|
|
148
|
nodes.resetFlags();
|
|
149
|
return nodes.contains(source);
|
|
150
|
}
|
|
151
|
|
|
152
|
static boolean isConstrained(Node left, Node right) {
|
|
153
|
Subgraph common = left.getParent();
|
|
154
|
while (common != null && !common.isNested(right)) {
|
|
155
|
left = left.getParent();
|
|
156
|
common = left.getParent();
|
|
157
|
}
|
|
158
|
while (right.getParent() != common)
|
|
159
|
right = right.getParent();
|
|
160
|
return (left.rowOrder != -1 && right.rowOrder != -1)
|
|
161
|
&& left.rowOrder != right.rowOrder;
|
|
162
|
}
|
|
163
|
|
|
164
|
}
|