1 package org.codehaus.plexus.util.dag;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 import java.util.HashMap;
20 import java.util.LinkedList;
21 import java.util.List;
22 import java.util.Map;
23
24
25
26
27
28 public class TopologicalSorter {
29
30 private static final Integer NOT_VISITED = 0;
31
32 private static final Integer VISITING = 1;
33
34 private static final Integer VISITED = 2;
35
36
37
38
39
40 public static List<String> sort(final DAG graph) {
41 return dfs(graph);
42 }
43
44 public static List<String> sort(final Vertex vertex) {
45
46 final List<String> retValue = new LinkedList<>();
47
48 dfsVisit(vertex, new HashMap<Vertex, Integer>(), retValue);
49
50 return retValue;
51 }
52
53 private static List<String> dfs(final DAG graph) {
54
55 final List<String> retValue = new LinkedList<>();
56 final Map<Vertex, Integer> vertexStateMap = new HashMap<>();
57
58 for (Vertex vertex : graph.getVertices()) {
59 if (isNotVisited(vertex, vertexStateMap)) {
60 dfsVisit(vertex, vertexStateMap, retValue);
61 }
62 }
63
64 return retValue;
65 }
66
67 private static boolean isNotVisited(final Vertex vertex, final Map<Vertex, Integer> vertexStateMap) {
68 final Integer state = vertexStateMap.get(vertex);
69
70 return (state == null) || NOT_VISITED.equals(state);
71 }
72
73 private static void dfsVisit(
74 final Vertex vertex, final Map<Vertex, Integer> vertexStateMap, final List<String> list) {
75 vertexStateMap.put(vertex, VISITING);
76
77 for (Vertex v : vertex.getChildren()) {
78 if (isNotVisited(v, vertexStateMap)) {
79 dfsVisit(v, vertexStateMap, list);
80 }
81 }
82
83 vertexStateMap.put(vertex, VISITED);
84
85 list.add(vertex.getLabel());
86 }
87 }