Topological sort
トポロジカルソート*1を書いてみました。C言語、D言語、Lua、Rubyで。
トポロジカルソートが何に使えるかというと、makeの依存性解決などで使えます。yamakeというビルドシステムを作る上で、参考にしているシステムとしてninja*2のソースコードを見ていたのですが、自分でもできそうだと思ってやってみました。ninjaではトポロジカルソートっぽいことはやってませんが。
実装は簡単でしたが、依存性解決にトポロジカルソートが使えるということを探すまでに少し時間がかかりました。最初は循環参照検出*3のFloyd's cycle-finding algorithmにたどり着きましたが、makeの依存性のような二次のものには対応できないのでさらに探していたらなんとか見つかったという感じです。
