KahnSorter implements TopologicalSorter<T> { @Override public List<T> sort() { List<T> resultList = Lists.newArrayList(); while (!openNodes.isEmpty()) { T node = openNodes.iterator().next(); openNodes.remove(node); resultList.add(node); for (T dependent : dependentsLookup.removeAll(node)) { int dependencies = 0; if (dependencyCount.containsKey(dependent)) { dependencies = dependencyCount.get(dependent) - 1; dependencyCount.put(dependent, dependencies); } else { dependencyCount.put(dependent, 0); } if (dependencies == 0) { openNodes.add(dependent); } } } if (!dependentsLookup.isEmpty()) { throw new CircularDependencyException("Could not sort nodes, one or more circular dependencies exist involving: " + dependentsLookup.keySet()); } return resultList; }  @Override void addNode(T node); @Override void addNodes(Collection<T> nodes); @Override void addEdge(T fromNode, T toNode); @Override List<T> sort();  }
@Test public void trivialSort() { assertEquals(Lists.newArrayList(), sorter.sort()); }