graph - 到達可能性に関するブール制約を使用して DAG を検索する

Question

クエリは次のようなものです

((A および (B または C)) から到達可能) かつ ((D および E) から到達不能) であるすべての頂点を返します。

クエリは、到達可能性に関するあらゆる種類のブール制約で形成できます。

このクエリを高速に実行する効率的な方法はありますか? 実際にすべてのアイテムの到達可能な頂点のセットを見つける以外に、それらのセットで和集合、交差、およびマイナスを設定しますか?

Answer 1

あなたが提案するデフォルトよりも検索を高速化する唯一の方法（述語の各頂点から到達可能なセットを計算し、次にセット演算を行う）は、検索中にブール演算を行い、それを使用して中止することだと思います枝。

たとえば、((A または B) から到達可能で、C から到達できない) セットを計算しようとしているとします。ノードを検索するとき、(B) とマークされたノードにいて、「次の」ノードの 2 つが既にそれぞれ (A) と (C) とマークされている場合。これら 3 つのノードでは、述語は次のように短縮されます。

(B): P = NOT(C)
(A): P = NOT(C)
(C): P = FALSE

したがって、これらのノードのいずれかに検索を続行する理由はありません。

(当然、同じ DAG で複数のセットを計算する場合は、これらのマークを保持する必要があります。)