2009-07-01から1ヶ月間の記事一覧

有向グラフを強連結成分に分解するアルゴリズム

CormenのIntroduction to Algorithmsには,グラフGと有向辺を逆にしたG_revに対してそれぞれDFSする方法が紹介されている.これは,わかりやすいアルゴリズムではあるのだけれど,逆グラフを求める必要があるのが玉にキズである.一方,SedgewickのAlgorithm…

DSからCPSの関数を呼び出す方法

CPSからDS(Direct Style)の関数を呼び出すのは,以下のように何の問題もなくできる. fun f_cps(k, x) = let t = g_ds(x) in ... (k t) // リターン ではその逆はどうか? DSの関数は,現在の継続を明示的にパラメータとして渡されていないので,呼び出した…