DirectedGraph { public List<T> getTopologicalSort(Comparator<T> tieBreaker) { List<T> order = new ArrayList<T>(); DirectedGraph<T> g = new DirectedGraph<T>(this); while (true) { Set<T> nodes = g.getNodes(); if (nodes.isEmpty()) return order; List<T> noInbound = new ArrayList<T>(); for (T node : nodes) { if (g.getInboundNodes(node).isEmpty()) noInbound.add(node); } if (noInbound.isEmpty()) throw new IllegalStateException("cycle"); if (tieBreaker != null) Collections.sort(noInbound, tieBreaker); T node = noInbound.get(0); order.add(node); g.removeNode(node); } } DirectedGraph();  DirectedGraph(DirectedGraph<T> graph); Set<T> getNodes(); Set<Pair<T>> getEdges(); Set<T> getInboundNodes(T node); Set<T> getOutboundNodes(T node); boolean isConnected(T from, T to); void addNode(T node); void addEdge(T from, T to); void removeEdge(T from, T to); List<T> getTopologicalSort(Comparator<T> tieBreaker);  }
@Test public void testGetTopologicalSort() { DirectedGraph<String> graph = new DirectedGraph<String>(); graph.addEdge("a", "b"); graph.addEdge("b", "c"); graph.addEdge("c", "d"); graph.addEdge("d", "e"); List<String> s1 = graph.getTopologicalSort(null); assertEquals(5, s1.size()); assertEquals(Arrays.asList("a", "b", "c", "d", "e"), s1); }