1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
package org.eclipse.papyrus.infra.elementtypesconfigurations.utils;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import org.eclipse.papyrus.infra.elementtypesconfigurations.ElementTypeConfiguration;
import org.eclipse.papyrus.infra.elementtypesconfigurations.SpecializationTypeConfiguration;
//Implements Tarjan's strongly connected components algorithm
public class ElementTypeCycleUtil {
protected static Collection<Collection<String>> computeStronglyConnectedComponents(Set<String> vertices, Map<String, List<String>> edges) {
int index = 0;
Map<String, Integer> lowIndex = new HashMap<String, Integer>();
Collection<String> visitedVertices = new HashSet<String>();
Stack<String> stack = new Stack<String>();
Collection<Collection<String>> stronglyConnnectedComponents = new ArrayList<Collection<String>>();
for (String vertex : vertices) {
if (!visitedVertices.contains(vertex))
dfs(vertex, vertices, edges, stronglyConnnectedComponents, stack, lowIndex, visitedVertices, index);
}
return stronglyConnnectedComponents;
}
protected static void dfs(String vertex, Set<String> vertices, Map<String, List<String>> edges, Collection<Collection<String>> stronglyConnnectedComponents, Stack<String> stack, Map<String, Integer> lowIndex, Collection<String> visitedVertices, int index)
{
lowIndex.put(vertex, index++);
visitedVertices.add(vertex);
stack.push(vertex);
int minIndex = lowIndex.get(vertex);
for (String targetVertex : edges.get(vertex))
{
if (!visitedVertices.contains(targetVertex))
dfs(targetVertex, vertices, edges, stronglyConnnectedComponents, stack, lowIndex, visitedVertices, index);
if (lowIndex.get(targetVertex) < minIndex)
minIndex = lowIndex.get(targetVertex);
}
if (minIndex < lowIndex.get(vertex))
{
lowIndex.put(vertex, minIndex);
return;
}
List<String> component = new ArrayList<String>();
String memberVertex;
do
{
memberVertex = stack.pop();
component.add(memberVertex);
lowIndex.put(memberVertex, vertices.size());
} while (!memberVertex.equals(vertex));
if (component.size() > 1) {
stronglyConnnectedComponents.add(component);
}
}
static public Collection<Collection<String>> getCycles(Collection<ElementTypeConfiguration> elementTypesConfigurations) {
Map<String, List<String>> edges = new HashMap<String, List<String>>();
Set<String> vertices = new HashSet<String>();
for (ElementTypeConfiguration elementTypeConfiguration : elementTypesConfigurations) {
String currentElementTypeID = elementTypeConfiguration.getIdentifier();
// Add current to the vertices
vertices.add(currentElementTypeID);
// Add dependencies vertices
if (elementTypeConfiguration instanceof SpecializationTypeConfiguration) {
for (String specializedTypeID : ((SpecializationTypeConfiguration) elementTypeConfiguration).getSpecializedTypesID()) {
vertices.add(specializedTypeID);
if (edges.get(specializedTypeID) == null) {
edges.put(specializedTypeID, new ArrayList<String>());
}
}
edges.put(currentElementTypeID, ((SpecializationTypeConfiguration) elementTypeConfiguration).getSpecializedTypesID());
} else {
edges.put(currentElementTypeID, Collections.<String> emptyList());
}
}
return computeStronglyConnectedComponents(vertices, edges);
}
}
|
