Topological Sort

Following Corky’s suggestion, I’ve been trying to view the whole thing more as a graph problem than a combinatorics problem. I still think generating permutations would be the most efficient way, but I can’t figure out how to limit the generator to just legal schedules: If I just generate all permutations, I might schedule a thread before it has been forked, or after it has been joined and is therefore presumed dead.

Just approaching it as a graph search problem, e.g. depth-first, doesn’t seem to be enough, though, because we’re not interested in just ONE way to cover the graph, we’re interested in ALL ways to cover the graph. So I’m still trying to combine graph algorithms with permutations.

One way that I might to is collapse the graph as much as possible, i.e. remove consecutive nodes with just one inbound and one outbound arrow. Then I could run a topological sort to figure out in which order the forks and joins need to happen.

Maybe from that I can even figure out which threads I need to schedule concurrently.

Of course, on the other hand, I can still generate all possible permutations and then remove the permutations that violate scheduling protocols.


About Mathias

Software development engineer. Principal developer of DrJava. Recent Ph.D. graduate from the Department of Computer Science at Rice University.
This entry was posted in Concurrent Unit Testing. Bookmark the permalink.

Leave a Reply