public static < T > void topologicalSort ( final List < Vertex < T > > vertices ) throws CyclicDependencyException { // Verify the graph and set the vertex orders in the process. verify ( vertices ) ; // We now that there are no cycles and that each of the vertices has an order // that will allow them to be sorted. Collections . sort ( vertices ) ; }
Sort a set of vertices so that no dependency is before its vertex . If we have a vertex named Parent and one named Child that is listed as a dependency of Parent we want to ensure that Child always comes after Parent . As long as there are no cycles in the list we can sort any number of vertices that may or may not be related . Both Parent and Child must exist in the vertices list but Child will also be referenced as a dependency of Parent .