昨日の記事
でトポロジカルソートのことを書きましたので、ＰＨＰでコーディングしてみました。
試しに「風が吹けば桶屋が儲かる」の論法をランダムに並べて、トポロジカルソートを使って並べ替えてみます。
■読み込むデータファイル内容（tsort.txt）
風が吹く 桶屋が儲かる
三味線弾きが増える 三味線が売れる
ねずみが増える ねずみが桶をかじる
砂が目に入って失明する 三味線弾きが増える
ねずみが桶をかじる 桶がなくなる
猫が殺される ねずみが増える
風が吹く 砂ぼこりが舞う
桶がなくなる 桶を買う人が増える
砂ぼこりが舞う 砂が目に入って失明する
桶を買う人が増える 桶屋が儲かる
三味線が売れる 猫が殺される
■トポロジカルソート（tsort.php）
<?php
error_reporting(E_ALL);
ini_set("display_errors", 1);
$file= "tsort.txt";
foreach (tsort($file) as $value) echo $value,"<br />\n";
function readmap($file)
{
$map= $order= array();
if (file_exists($file) and $fp=fopen($file, "rb")){
while (($line=fgets($fp)) !== false){ // 一行ずつ読み出す
// 切り出す
if (!preg_match('/(\S+)\s+(\S+)/', $line, $match)) continue;
// ベクトルを２次元配列にマッピングおよび全ワードをnull値で初期化
$map[$match[1]][$match[2]]= $order[$match[1]]=
$order[$match[2]]= null;
}
fclose($fp);
}
return array($map, $order);
}
function tsort($file)
{
list($map, $order)= readmap($file); // ファイルデータ切り出し
$order= _tsort($order, $map, count($order)); // トポロジカルソート
// null値が残っていればＮＧ（空配列を返す）
if (array_search(null, $order)) return array();
arsort($order); // 値順に並び替え
return array_keys($order);
}
function _tsort(&$order, &$map, &$count)
{
$pointed= $checklist= array();
foreach (array_keys($order) as $param){
if ($order[$param] !== null) continue;
$checklist[]= $param; // 順番未確定のものを集める
if (isset($map[$param]))
foreach (array_keys($map[$param]) as $right)
$pointed[$right]= 1; // ポイントされてるものをセット
}
// ポイントされてないものに順番を振る
foreach ($checklist as $value){
if (!isset($pointed[$value]) && $order[$value] === null){
$order[$value]= $count--;
unset($map[$value]);
$count && _tsort($order, $map, $count);
break;
}
}
return($order);
}
?>
[出力結果]
風が吹く
砂ぼこりが舞う
砂が目に入って失明する
三味線弾きが増える
三味線が売れる
猫が殺される
ねずみが増える
ねずみが桶をかじる
桶がなくなる
桶を買う人が増える
桶屋が儲かる
うまくいったようです。。 ∩( ・ω・)∩ばんじゃーい
