安心してください。AWKですから。【トポロジカルソート篇】

定期的に思うことですが、アルゴリズム力がないので諸々のアルゴリズムの復習をします。 最も書き慣れている言語のうちのひとつで、結構書きやすいと思うのでAWKで書くことにします。(布教の意味も込めて)

今回はトポロジカルソートを書こうと思います。トポロジカルソートと言えばGNU coreutilsでtsortとして実装されていることがシェルっぽい人のなかでは有名だと思います。 そうは言ってもシェルスクリプトの中でどうやったら上手く使えるのかはわかりません。 トポロジカルソートは入力に対して答えが一意に定まらないのでtsortとは結果がかわるかもしれません。

アルゴリズムの説明

細かい説明はWikipediaを参照してください。トポロジカルソートでは入力として有向グラフが与えられます。出力は有向グラフのnodeを、edgeの向きが逆転しないようにした順序になります。トポロジカルソートの解は一般に一意に定まりません。 有向グラフがリソースの依存関係を表わしていると考えるとき、トポロジカルソートの出力は依存関係を満たすようなbuildなどの順序になります。有向グラフがpartial orderを表わしていると考えるとき、total orderに拡張していると見ることもできます。

プログラムの仕様

AWKでは(gawkでは独自拡張で実装されてますが)多次元配列がなく、一次元の連想配列しかありません。 そのためグラフの辺の情報を

edge[source] = target0 target1 target2 ... targetn

のように空白区切りで実装しています。 sourceに向う辺を検索する部分は、各nodeについてsourceに向かう辺があるかどうかを線形に探索しています。 辺を削除した結果どこにも向う辺がないnodeについては、空白のtargetを代入することで実装しています。

入力はtsortとほぼ同じですが、各行ごとにsourceとtargetのnodeを書く必要があります。出力はtsortと同じ仕様です。

	#!/usr/bin/gawk -f
	# @file topsort.awk
	# @brief perform topological sort in awk
	# @note tested in gawk 4.1.3, mawk 1.3.4, and nawk
	{
	edge[$1] = edge[$1]" "$2;
	}
	END {
	do {
	last_sources = "";
	for (i in edge) {
	last_sources = last_sources" "i;
	}
	for (source in edge) {
	found = 0;
	for (s in edge) {
	split (edge[s],targets," ");
	for (j in targets) {
	if (source == targets[j]) {
	found = 1;
	break;
	}
	}
	if (found) {
	break;
	}
	}
	if (!found) {
	print source;
	split(edge[source],targets," ");
	for (i in targets) {
	if (!(targets[i] in edge)) {
	edge[targets[i]] = "";
	}
	}
	delete edge[source];
	}
	}
	now_sources = "";
	for (i in edge) {
	now_sources = now_sources" "i;
	}
	} while (now_sources != last_sources);
	if (length(last_sources) != 0 ) {
	print "loop found!!";
	}
	}

view raw topsort.awk hosted with ❤ by GitHub

	7 11
	7 8
	5 11
	3 8
	3 10
	11 2
	11 9
	8 9
	11 10

view raw topsort.in hosted with ❤ by GitHub