私は長い間有向非巡回グラフ（DAG）に興味を持っていましたが、ウィキペディアでトポロジカルソートについて読んだ後、レイヤーの番号付けを含むアプローチについて特別な言及は見つかりませんでした（ただし、レイヤーは描画のために広く言及されています）。このアプローチでは、グラフは技術的にトポロジカルソートされませんが、すべてのノードにレイヤー（レベル）の正しい番号が含まれていることを知っているので、特定のノードが別のノードよりもトポロジカルに「大きい」かどうかを常に判断できます。一方、順序付きリストがない限り、ノードをトポロジ的に列挙することはできません（ただし、これは、ノードのレベルを比較する最終的な従来の並べ替えで実行できます）。
このアプローチにより、レベル情報の正確性を維持しながら、任意の接続を実装できます。手順は次のとおりです。
- 新しく追加されたノード（接続なし）の場合、適用されるレベルは1です。
- 2つのノード間の接続が要求され（mからnまで）、n.level> m.levelの場合、それらは単に接続されているだけであり、他のノードのレベル固定は必要ありません。
- 要求された接続（mからn）n.level <= m.levelの場合、n.levelを（m.level + 1）に変更し、nの依存関係を再帰的にチェックして、同様のレベルの増加を確認します（または、レベルが増加しない場合は増加しません）。再帰ステップでは互換性があります）。
- 再帰的に入力されたノードのリストを保持すると、循環して何らかの取り消し操作を実装する試みを検出できます（影響を受けるすべてのノードのレベルを以前の値に戻します）
既知のノードとそれらの間の接続のセットについて、level = 1を適用するすべてのノードをそれらに追加し、それらの間のすべての既知の接続を適用しようとします（ciclesを無視して元に戻します）。
最終レベルの情報では、ノードをトポロジ的に比較できるだけでなく、他の有用な情報も含まれています。例えば：
- レベル=1のすべてのノードには着信接続がありません（すべてのパスはそれらの1つから始まります）。したがって、DAG列挙はそれらから開始できます。
- 最長のパス（エッジの数）は、（最大レベル+ 1）より長くすることはできません
一部の人工データ（nノード、Node（n + 1）に接続されているすべてのNode（n））の場合、このアルゴリズムは非常に遅くなる可能性があると思います。しかし、私が試した実際のデータ（Wikipediaのカテゴリ-800,000ノード-2,000,000接続）の場合、時間はまともで（5〜10分）、レベルとサイクルの試行回数は少ない（369レベル、1000サイクルの試行）
では、この方法は新しいものですか、それともよく知られていますが、ウィキペディアやその他のリソースでは広く紹介されていませんか？それは（技術的には）一種ではないので、データ再構築と呼ばれるべきですか？