algorithm - データの局所性を最大化するために、メモリ内に有向非巡回グラフをレイアウトするためのアルゴリズム

Question

私はエッジを持っていると言う

A -> C
A -> D
A -> E
B -> D
B -> E

データの局所性を最大化するために、DAGをこの順序でメモリに（配列として）格納し、ノードとその依存関係の間の距離を最小化するように調整します。

C, A, D, E, B

そのため、Aの距離は1からC、1からD、2からEになります。

そして、そのBの距離は1からE、2からDです。

これを行うアルゴリズムの名前はありますか？そうでない場合、これをどのように実装しますか？

Answer 1

DAGを線形化したいようです。依存関係の解決に使用しているかどうかはわかりません。Topological_sortingあなたの質問に馴染みがあるようです。また、プログラムtsortは非常に似たようなことをします。

ただし、これは依存関係の線形化です。

neel@gentoo:~$ tsort
C A
D A
E A
D B
E B

C
D
E
B
A

これは、そのタスクを実行する必要がある順序を出力します。サイクルがあると動作しなくなります。あなたがその非周期的であると述べたように、それは関連性があります。

data locality ordering stringそのようなアルゴリズムやそれに類似したものがあるかどうかはわかりませんが、データの局所性文字列に問題があるようです。

データの局所性文字列でどのように表現しCますか？ABBA

私は今あなたが何をしたいのか正確にはわかりません。依存関係を最小化してタスクを適切な順序で実行する場合は、トポロジカルソートを実行します。

Answer 2

局所性を改善するためのわずかに異なるアプローチは次のとおりです。

http://ceur-ws.org/Vol-733/paper_pacher.pdf

説明されているアルゴリズムは、トポロジカルソートよりも力指向グラフ描画アルゴリズムに近いようです。

imGraphなどのメモリ内グラフデータベースに関する論文も読む必要があります