無効なパスをグラフに定義する

Question

ほとんどの場合、通常の有向グラフが適しているというプロジェクトに取り組んでいます。しかし、私たちのグラフではいくつかのパスを無効にしたい。たとえば、グラフが：

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

である場合、A-> B-> Cは有効なパスですが、A-> D-> Cはそうではありません。無効なパスをどこかに定義して毎回検証チェックを行うことができますが、アプリケーションがグラフに大きく依存するため、これは重要なパフォーマンス上の問題を引き起こします。

このような状況のための特殊なデータ構造やアルゴリズムはありますか？

おかげ

Answer 1

あなたはそうあなたはそれがCからに行くことができるノードのリストにないため、AからのパスはCに行くことができないことを知っているfrom:list(to)の各ノードでのマッピングを格納することができ深度が1より大きい場合は、それまでのノードのタプルは、その1つのノードではなくキーとなります。これは、eBGPがインターネットルーティングのためにどのように動作するかとよく似ています。

あなたが説明しているようなデータ構造を使用することに決めた場合は、どうしたらいいのかチェックする必要があります。どちらの場合も、状況ごとに複数のグラフを格納できます。