Recently I'm doing a lot of ExtJS work. In complex JS app developement you'll quickly have a LOT of files to link to your HTML document. You'll want to combine and compress these files for production and link them sperate and uncompressed for testing.

The simplest solution is just listing the files in a configuration file. But managing this list is a PITA. We're developers, not clerks. So I decided this list should be auto-generated and properly sorted. Scanning the filesystem for javascript files is trivial, and I quickly decided the sort order should be determined by examining the contents, looking for class names. All files contain classes, with a JSDoc declaration of @class app.module.ClassName, so it's not hard to establish which file depends on which.

The real issue is sorting. Before long I came to the conclusion that there's no out of the box solution for the type of sorting I needed, all sort functions use QuickSort, even the ones using UDFs. On WikiPedia, I found that what I needed "resolving dependencies into an ordered list" could be accomplished using a different algorithm called "Topological sorting".

WikiPedia describes one implementation in pseudo code:

L ← Empty list that will contain the sorted elements

S ← Set of all nodes with no incoming edges

while S is non-empty do

remove a node n from S

insert n into L

for each node m with an edge e from n to m do

remove edge e from the graph

if m has no other incoming edges then

insert m into S

if graph has edges then

output error message (graph has at least one cycle)

else

output message (proposed topologically sorted order: L)

I decided to create a PHP implementation of this algorithm.