Excelシート循環参照をトポロジカルソートで判定してみる(1/3)

こんにちは！アルダグラムでレポートチームのエンジニアをしている志茂です。

レポートチームでは、お客様が利用されているExcelファイルをKANNA上にアップロードし、Webから編集できるような機能を開発しております。

Excelファイルを読み込み編集できるようにするためには、色々な考慮事項があるのですが、今回はその中でもExcelアップロード時にバリデーションが必要な、Excelシートの循環参照をトポロジカルソートを用いて判定する方法について、以下のように3回に分けてお話ししたいと思います。

• Excelシートの循環参照をトポロジカルソートで判別するためには (1/3)
• DFS（深さ優先探索）を利用したトポロジカルソート (2/3)
• BFS（幅優先探索）を利用したトポロジカルソート (3/3)

Excelの循環参照について

まず基本的なExcel仕様についてですが、
エクセルのセルやシートを参照する際に、自身のセルやシートを参照してしまうと正しく計算が行われない可能性があるので、循環参照を含んだシートはアップロード時にバリデーションエラーを返す必要があります。
Excel で循環参照を削除または許可する
ちなみにスプレッドシートでも循環参照をすると以下のようなエラーメッセージが表示されます。

上記のエラーを発生させないために、Excelのアップロード時に循環参照をバリデートして、アップロードエラーを返しております。

トポロジカルソートとは

トポロジカルソートとは、有向非巡回グラフ（Directed Acyclic Graph: DAG） などで、必ずどのノードもエッジの出力先のノードより前に来るように位置する並び替えを指します。

とりあえず手を動かして、前情報なしでやってみたい！！という方は、
こちらのLeet codeでチャレンジしてみてください。
Leet code 207. Course Schedule

チャーハン🍚の作り方でノードとエッジを表現してみる

この説明だけだとピンとこないと思うので、
イメージを掴むためにチャーハンの作り方を例に出しながら説明したいと思います。ちなみに私の実家ではチャーハンを焼き飯と言うのですが、我が家だけでしょうか。

トポロジカルソートは、特に順序付きのタスクがある際に、事前に終わらせておく必要があるタスクを管理するのに役立ちます。チャーハンの作成タスクと実行順序をまとめてみました。

必要なタスク(ノード)
A: ご飯を炊く
B: 材料を切る（ネギ、卵、ハムとか）
C: フライパンを温める
D: 卵を炒める
E: ご飯を炒める
F: 調味料を加える
G: 完成したチャーハンを皿に盛る

タスク間の依存関係(エッジ)
A -> E: ご飯が炊けないと炒められない
B -> D: 材料が切れないと卵を炒められない
C -> D: フライパンを温めないと卵を炒められない
D -> E: 卵を炒めてからご飯を炒める
E -> F: ご飯を炒めた後に調味料を加える
F -> G: 調味料を加えた後に皿に盛る

有向非巡回グラフとは

上記のノード(タスク)と依存関係(エッジ)をモデル化するのに有効なグラフデータ構造の一種です。上記の例を図示すると以下のような図になります。

チャーハンの例で言えば、ご飯がないと炒められないので、Eより前にAを実行してタスクを完了する必要がありますが、別に材料を切ってからご飯を炊いても問題はありません。全ての事前に終わらせないといけない作業が、全ての終わらせないといけない作業の前に来るように並び替えることがトポロジカルソートになります。

上記の例の場合、並び替えのパターンがいくつかあり、トポロジカルソート実行後は以下のように並び替えることができます。
B → C → D → A → E → F → G
C → B → A → D → E → F → G

上記ようにソートすることにより、どのタスクからスタートしてもタスクの依存関係上問題なく(途中からの場合、まともなチャーハンはできないですが。。。)、完了できます。

Excelシート循環参照を有向非巡回グラフで検知する

有向非巡回グラフは、閉路のない有向グラフのことであることが前提のデータ構造になります。閉路が存在する場合（さっきの例であれば、サイクルがあると永遠にチャーハンが出来上がりません。）が存在しないため、ある頂点から同じ頂点に戻ってこれないという特徴があります。

有向（Directed）:
グラフのエッジ(辺)には方向があり、ノード(頂点)間の一方向の関係を示します。

非巡回（Acyclic）:
グラフ内に閉路(サイクル)が存在しないこと。つまり、あるノードから出発して同じノードに戻るようなパスが存在しません。

このある頂点から同じ頂点に戻ってこれないという特徴を活かして、取得したシートのデータに対してトポロジカルソートを行い、閉路があった場合は循環参照が発生しているとして、バリデートエラーを投げるようにしています。

ExcelのシートA〜Eの5件あった場合、各シート内のセルの参照に閉路がない（循環がない）を以下のような有向非巡回グラフで表すことができます。

循環参照(閉路)がない場合、セルの指定は省略しております。

循環参照(閉路)がある場合

上記の例で、トポロジカルソートを行うと、以下のような結果のどれかを得ることができます。

A → B → D → C → E
A → D → B → C → E
D → A → B → C → E
D → B → A → C → E

最後に

以上、Excelシートの循環参照をトポロジカルソートで判定してみる (1/3) でした。今回は具体的なコードを後回しにして、概念を具体例をもとに簡単にお話しさせていただきました。

次回以降はみんな大好きKotlinで実際にコードを書いて、循環参照を検知したいと思います。
トポロジカルソートを実現するためには、深さ優先探索（DFS）で解く場合と幅優先探索（BFS）で解く場合の2種類があるので、2回に分けてお話しさせていただこうと思います。

もっとアルダグラムエンジニア組織を知りたい人、ぜひ下記の情報をチェックしてみてください！