blob: 3f4feec1a572892dfa9d47bedc0bb8ed0e5f291d (
plain) (
blame)
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
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.config.model.graph;
import com.yahoo.component.ComponentId;
import java.util.*;
/**
* A model graph contains the dependency graph of config models.
*
* @author Ulf Lilleengen
* @since 5.1
*/
public class ModelGraph {
private final List<ModelNode> modelNodes;
private final List<ModelNode> roots;
public ModelGraph(List<ModelNode> modelNodes, List<ModelNode> roots) {
this.modelNodes = modelNodes;
this.roots = roots;
}
/**
* Performs a topological sort ot the models stored in this graph. The algorithm is based on Kahn topological sort.
*
* @return a sorted list of {@link com.yahoo.config.model.graph.ModelNode} in dependency order.
*/
public List<ModelNode> topologicalSort() {
DependencyMap dependencyMap = new DependencyMap(modelNodes);
Queue<ModelNode> unprocessed = new LinkedList<>();
unprocessed.addAll(roots);
List<ModelNode> sortedList = new ArrayList<>();
while (!unprocessed.isEmpty()) {
ModelNode sortedNode = unprocessed.remove();
sortedList.add(sortedNode);
for (ModelNode node : modelNodes) {
if (dependencyMap.dependsOn(node, sortedNode)) {
dependencyMap.removeDependency(node, sortedNode);
if (!dependencyMap.hasDependencies(node)) {
unprocessed.add(node);
}
}
}
}
for (ModelNode node : modelNodes) {
if (dependencyMap.hasDependencies(node)) {
throw new IllegalArgumentException("Unable to sort graph because it contains cycles");
}
}
return sortedList;
}
List<ModelNode> getNodes() {
return modelNodes;
}
private static class DependencyMap {
private final Map<ComponentId, Set<ComponentId>> map = new LinkedHashMap<>();
DependencyMap(List<ModelNode> modelNodes) {
for (ModelNode node : modelNodes) {
Set<ComponentId> ids = new LinkedHashSet<>();
ids.addAll(node.listDependencyIds());
map.put(node.id, ids);
}
}
public boolean dependsOn(ModelNode node, ModelNode sortedNode) {
return map.get(node.id).contains(sortedNode.id);
}
public void removeDependency(ModelNode node, ModelNode sortedNode) {
map.get(node.id).remove(sortedNode.id);
}
public boolean hasDependencies(ModelNode node) {
return !map.get(node.id).isEmpty();
}
}
}
|
