Structuring File Storage: Organizing Data Units within Acyclic Graph Folder Architectures
ためしにChatGPTでタイトルを提案してもらった。
DG
有向グラフ構造一般の話からスタートする
incoming edgeを持たないノードは initial node と呼ぶ。
outgoing edgeを持たないノードはterminal node と呼ぶ。
どんなノードもinitial nodesとterminal nodesとそれ以外に分類できる
「それ以外」のノードは intermediate nodes と呼ぼう。
DAG
DAGであること以外に何も仮定しないところからスタートする
つまりエッジにもノードにも何ら属性を持たない状態から考える。
DAGならmultipartiteレイアウトで描画できる
ただしどのノードがどのレイヤに属するかについては唯一に決まらない
https://gyazo.com/6f8e5c2c988fbd00bcf168a4b6e003f9
Top and Bottom
一般に有向グラフにおいて
全てのinitial nodesへのエッジを持つtop nodeを追加できる
全てのterminal nodesからのエッジを持つbottom nodeを追加できる
DAGにtop nodeとbottom nodeを追加しても非循環性を損なわない
https://gyazo.com/827b82179ac1c76fd1574ba6cf6e13c0
エッジが名前を持つ
各ノードのIDが分かっているならID一発でノードを特定できる
各ノードのIDが分からないなら名前のリストでノードを特定する
パスとはtop nodeからのエッジの列である
ノードを指定してもパスは一意に決まらない可能性がある
あるノードに対してその親ノードが複数あり得る
フォルダには識別子がある。
たとえばGoogle DriveではフォルダにもファイルにもIDが付与されている。
フォルダのIDもファイルのIDも単に "id" と呼ばれている。
IDは親子関係を持ち、そのグラフ構造はアサイクリックである
関連