Topological Sort

I’ve been working on a new mac app and recently stumbled across a problem. I had a set of ‘actions’ which each had dependency values. i.e. One ‘action’ had to perform before another ‘action’ could. I needed some way of sorting these ‘actions’ in order to list them in the correct processing order, kinda of like a flowchart.

With the help of Google I found out that this type of problem is actually a graph theory problem which could be solved using a Topological Sort.

It took me a while to get my head around it, but with the help of the algorithm on the wikipedia page I was able to get an Objective-C version written and working in a few hours.

Programming can be frustrating at times, but it’s so rewarding if you stick it out and manage to work out a solution.