この記事は ひとりアドベントカレンダーRosettaCodeで楽しむプログラミング Advent Calendar 2025の18日めの記事です。
オイラー閉路を発見するための効率的な方法、とあるが、リンク先のpedia.deは他の言語に翻訳されていない、独自研究のような雰囲気。
示されているアルゴリズムを、翻訳と、内容の再調整をしながら引き写す。
事前条件preconditionを宣言しておきながら、アルゴリズムでまず VerifyEulerianCircuit() をしている部分は見なかったことにする。
割とimmutableに書きたいアトモスフィアを感じるが、命令的にかかないといけないという呪縛のせいでいびつになっている。
Circuit, Stack だけが状態（変数）のように見せて、実はグラフGも変更するのがその最たるところ。
出発する頂点の選択について degree(v) > 0 と条件を付けているが、前提条件からそうでないものなどない。（グラフが |V| = 1 でもない限り。）
currentをStackとは別物として扱っているが、多分Stackのtopがcurrentになっている。
実装見本らしいOCaml版でもそうしていて、この擬似コードとは違っている。
メインループ while の中の if の前後を変えた。先に動く方を前に置いた方がわかりやすいと思う。
入力 グラフG=(V,E)
事前条件
・グラフは強連結
・全ての頂点の入り次数と出次数が等しい
出力 頂点のリストとして、オイラー閉路
手続き
Circuit ← FindEulerianCircuit(G)
Circuitが全ての辺を含むなら成功、さもなくば存在しない
Function FindEulerianCircuit(Graph G):
Circuit ← 空リスト // 確定したオイラー閉路を後ろから積み上げるリスト
Stack ← 空スタック // 頂点のスタック
// 出発点を任意に選ぶ
current ← V中の任意の頂点v ただしvの次数 > 0 // 条件付けなくてもそんなのしかない。
// current を Stack にpushする // 多分これは嘘。一つ多くなってしまう
While Stack が空でない：
// 未使用辺がまだあるなら、それを辿る
if currentの出次数 > 0:
current を Stack にpushする
next ← currentの任意の隣接頂点
currentからnextへの辺をGから削除する
current ← next
else:
// 未使用辺が無くなったら閉路に追加する
currentをCircuitの先頭に追加する
current ← Stackからpopした頂点
Return Circuit
タスク指示に「OCaml版と同じ例で試せ」とあるように、それがお手本なのだろう。
と思って眺めると、while とか書いてあってほぼこの擬似コードに近くて、あれ？OCamlって命令型言語でしたっけ？という錯覚に陥る。
Haskell化
Stackは頂点のリストで表現できる。
currentは実はそのスタックトップであると解釈する。
Circuitはそのまま頂点のリストとする。
グラフは、頂点を連続する Int、隣接リストを Array Int [Int] で表現するとして、immutableに関数的に書くと、このアルゴリズムは擬似コードよりもコンパクトになる。
グラフの辺をもいでいくので Data.Array.Diff としているが、別に普通の Data.Array でも動く。
import Data.Array.Diff
findEulerianCircuit :: DiffArray Int [Int] -> Maybe [Int]
findEulerianCircuit graph0 = go graph0 [] [start]
where
start = fst $ bounds graph0 -- 添え字の下限から開始
go graph circuit [] -- スタックが空になったら終了
| all null (elems graph) = Just circuit -- 辺が尽きていたら成功
| otherwise = Nothing
go graph circuit (current:stack)
| null edges = go graph (current:circuit) stack -- 辺が尽きているとき、currentをstackからcircuitへ移す
| otherwise = go graph1 circuit (next:current:stack) -- まだあるならnextへ進む
where
edges = graph ! current -- currentの出辺
next = head edges -- 任意にnextを選ぶ
graph1 = graph // [(current, tail edges)] -- current→nextの辺を削除
graph1, graph2 :: DiffArray Int [Int]
graph1 = listArray (0,2) [[1],[2],[0]]
graph2 = listArray (0,6) [[1,6],[2],[0,3],[4],[2,5],[0],[4]]
ghci> findEulerianCircuit graph1
Just [0,1,2,0]
ghci> findEulerianCircuit graph2
Just [0,1,2,0,6,4,2,3,4,5,0]
さらに悪ノリすると、go 最後の7行を4行に圧縮もできる。
go graph circuit (current:stack) =
case graph ! current of
next:rest -> go (graph // [(current, rest)]) circuit (next:current:stack)
[] -> go graph (current:circuit) stack
おわりに
クワイン・マクラスキー法のときも思ったのだけど、リンクリストを繋ぎ直すだとか、in-placeな配列操作だとかが主眼なものでない多くのアルゴリズムは、命令型な擬似言語よりも関数型、データ不変な形で表現する方がよいのでは？という思いがますます強まりました。