仕事でとある処理を実装する際、下図のような階層構造をしたデータを扱うことになった。
最上位のどこを起点にしても配下は木構造（有向木）になっているので、例えば各ディレクトリに属するファイルを数えたい場合などは、普通の木構造に対するアルゴリズムで概ね上手くいく。
困ったのはアルゴリズムの選定ではなく、その考えをドキュメントに残すときだった。このグラフは部分的に見れば有向木だが全体を見れば有向木ではない。かといって有向非巡回グラフ（DAG）と言ってしまうと木構造に対するアルゴリズムで済むことを説明できない。「〇〇な DAG」と毎回特徴を添えるのは面倒。このグラフを簡潔に表す名前は無いだろうか？
グラフの特徴
思いつく特徴を挙げていくと、
- 有向非巡回グラフ（DAG）の一種
- 有向木と異なり、頂点には親が2つ以上ありうる
-
任意の2頂点を結ぶ有向パスは高々1つ
- ダイヤモンド状 ♦️ の繋がり（やショートカット）は存在しない
- 一方でバタフライ状 🦋 の繋がりはOKで、無向辺に置き換えるとパスは複数ありうる
- 任意の頂点から到達可能な頂点を抽出した部分グラフは有向木
- 任意の頂点へ到達可能な頂点を抽出した部分グラフは、有向木の逆向き
- 有向木でいう「根」がひとつとは限らない
- 親子関係を逆転させても同じ性質のグラフになる
DAG は前提として、太字にした事項が最も特徴的な気がする。これらの特徴が書いてあるグラフの説明を探した。
検索結果
調べたところ、 multitree という語句が見つかった。別名は strongly unambiguous graph や mangrove 。（マングローブという名前は根が複雑な木という感じで面白い）
https://en.wikipedia.org/wiki/Directed_acyclic_graph#Related_families_of_graphs の説明が簡潔かつ図入りでわかりやすい。
Related families of graphs
A multitree (also called a strongly unambiguous graph or a mangrove) is a DAG in which there is at most one directed path between any two vertices. Equivalently, it is a DAG in which the subgraph reachable from any vertex induces an undirected tree.
A polytree (also called a directed tree) is a multitree formed by orienting the edges of an undirected tree.
An arborescence is a polytree formed by orienting the edges of an undirected tree away from a particular vertex, called the root of the arborescence.
multitree という名前がどれほど一般的なのか、和訳はあるのか、など細かいところまでは分からず。
（あと、日本語で「有向木」と呼ぶものは英語では "directed tree" でなく "arborescence" や "directed rooted tree" らしい）
利用例
multitree は今回初めて見たので、普段の例は多くない気がする。通常のディレクトリのような単純な親子関係なら有向木で表せるし、複雑な依存関係なら DAG になるはず。
身近な例のひとつは家系図。血縁関係にある結婚（いとこ同士など）が無ければ、たしかに祖先から子孫までの経路はひとつに決まる。
プログラミング寄りで考えれば、多重継承の類を使ったクラスの継承関係は、菱形継承が無ければ multitree になる。
有向木を重ねるという方面から考えると、バージョン管理されたディレクトリが例として挙げられる（バージョン管理システム各種の内部的な仕組みの話ではなく、単に階層構造の話）。各バージョンにおけるディレクトリ構成はもちろん木構造だが、複数のバージョンを並べた場合は、更新の無かったファイルやディレクトリは同じものを参照して構わない。こうすればバージョン毎にコピーができてグラフが膨れ上がることを防げる。
例えば GitHub で適当なリポジトリを表示してみると、最終更新日時の異なるディレクトリやファイルが並んでいる。そのうち複数のブランチで同じ表示なものを開くと、ブランチに関わらず同じ内容が表示される。
3階層以上ある multitree を構成する際はダイヤモンド状の繋がりが含まれないよう注意を要するが、2階層ならその心配が無く必ず multitree になる。