数学屋さんは「いくつかの島に橋が架かった様子」をグラフ(Graph)といいます。
グラフのバリエーションとして、島に架かる橋が一方通行であるものを有向グラフ(Directed Graph)と称しております。
さらに有向グラフは大きく二つに分類されます。
ある島から一方通行の橋を渡っていけば元の島に戻れる経路のあるものを「閉路(cycle)のある有向グラフ」、
それと閉路のひとつもない「無閉路有向グラフ:DAG(Directed Acyclic Graph)」です。
DAGはエンジニアリングの分野と深い関わりがあります。
たとえばC/C++での#include関係はDAGになってますし、
.NETだとアセンブリの参照関係もDAGです。
クラスの継承もDAGですな。
あるいはお料理のレシピやmakefileなどの「手順書」もDAGです。
手順書がDAGでないと作業の堂々巡りが存在するわけで、いつまでたっても完了できひんです。
さて、とある有向グラフが与えられたとき、それがDAGであるか否かを判定するアルゴリズムを考えます。
[1] まず、有向グラフのデータとして橋の集合を用意します。橋には方向があるので"入口の島"→"出口の島"でひとつの橋を表現します。サンプルはコレ:
このグラフに引かれた矢印(つまり橋)を列挙すると:
A→B
A→C
B→C
C→D
の４本の橋が架かっています。
[2] 橋の入口を持つ島の集合を Iin, 出口を持つ島の集合をIoutとすると、
Iin = { A, B, C }, Iout = { B, C, D }
ですわね。ここで
Iin に含まれるが Iout に含まれない島の集合は { A }、
Iout に含まれるが Iin に含まれない島の集合は { D } です。
それぞれ 入ることのできない島/出ることのできない島の集合です。
こんな島は閉路の通り道にはなり得ません。閉路の通り道になるなら必ず入る橋と出る橋がそれぞれ一つ以上架かっているでしょうから。
そんなわけで、閉路の通り道となり得ない島(入れない島と出られない島)に架かる橋を取り除きます。
B→C
が残りました。
[3] 上の手順を繰り返します。
Iin = { B }, Iout ={ C }
ですから、このいずれかに架かる橋を取り除くと橋がなくなってしまいます。
閉路を構成する可能性のある橋がなくなった、てことは DAG です。
同じことを
こいつでやってみましょ。
A→B
B→C
C→A
C→D
ですから、
Iin = { A, B ,C }, Iout = { A, B , C, D }
IinとIoutのどちらかにしか含まれない島の集合は { D }、
{ D } に架かる橋を取り除くと:
A→B
B→C
C→A
もう一度。
Iin = { A, B, C }, Iout = { A, B, C }
どちらかにしか含まれない島はありません。Φ(空集合)です。
なのでこれ以上取り除ける橋はありません。
なのにまだ橋が残っています。なので DAG ではありません。
…んじゃまそゆことで、さくさくーっと実装してやんよ。
#include <iostream>
#include <algorithm>
#include <iterator>
#include <utility>
#include <set>
#include <vector>
using namespace std;
int main() {
typedef pair<char,char> dep;
vector<dep> deps;
#if 0
deps.push_back(dep('A','B'));
deps.push_back(dep('B','C'));
deps.push_back(dep('A','C'));
deps.push_back(dep('A','D'));
deps.push_back(dep('C','D'));
#elif 0
deps.push_back(dep('A','B'));
deps.push_back(dep('A','C'));
deps.push_back(dep('B','C'));
deps.push_back(dep('B','D'));
deps.push_back(dep('D','A'));
deps.push_back(dep('D','C'));
#elif 1
deps.push_back(dep('A','B'));
deps.push_back(dep('B','C'));
deps.push_back(dep('C','D'));
deps.push_back(dep('D','E'));
deps.push_back(dep('E','F'));
deps.push_back(dep('F','G'));
deps.push_back(dep('G','H'));
deps.push_back(dep('H','F'));
#endif
while ( true ) {
// 表示
for_each(deps.begin(), deps.end(),
[&](const dep& x) {
cout << x.first << "->" << x.second << endl;
});
cout << endl;
// 入口/出口セットを作る
set<char> parent;
set<char> child;
for_each(deps.begin(), deps.end(),
[&](const dep& x) {
parent.insert(x.first);
child.insert(x.second);
});
// 入口/出口セットの一方にあって他方にないものをdifに
vector<char> dif;
set_symmetric_difference(parent.begin(), parent.end(),
child.begin(), child.end(),
back_inserter(dif));
if ( dif.empty() ) break;
// 入口/出口のいずれかがdifにあればそれを削除
vector<dep>::iterator last = deps.end();
for_each(dif.begin(), dif.end(),
[&](char ch) {
last = remove_if(deps.begin(), last,
[=](const dep& x) {
return x.first == ch || x.second == ch;
});
});
deps.erase(last, deps.end());
}
if ( deps.empty() ) {
cout << "DAG!!" << endl;
} else {
cout << "cyclic!!" << endl;
}
}
あー、だれぞC#/VBにportしてはくれんかのぅ...