DirectedGraph { public List<V> topologicalSort() { Map<V, Integer> degree = inDegree(); Stack<V> zeroVertices = new Stack<>(); for (V v : degree.keySet()) { if (degree.get(v) == 0) { zeroVertices.push(v); } } List<V> result = new ArrayList<>(); while (!zeroVertices.isEmpty()) { V vertex = zeroVertices.pop(); result.add(vertex); for (V neighbor : neighbors.get(vertex)) { degree.put(neighbor, degree.get(neighbor) - 1); if (degree.get(neighbor) == 0) { zeroVertices.push(neighbor); } } } if (result.size() != neighbors.size()) { return null; } return result; }  void addVertex(V vertex); boolean containsVertex(V vertex); void removeVertex(V vertex); void addEdge(V from, V to); void removeEdge(V from, V to); List<V> getNeighbors(V vertex); Map<V, Integer> outDegree(); Map<V, Integer> inDegree(); List<V> topologicalSort(); List<V> reverseTopologicalSort(); boolean isDag(); @Override String toString();  }
@Test public void topologicalSort() { List<Character> result = graph.topologicalSort(); List<Character> expected = Arrays.asList('D', 'E', 'A', 'B', 'F', 'G', 'C'); assertEquals(expected, result); }