有向グラフ (具体的には制御フロー グラフ) があり、各頂点には一連のプロパティがあります。
Vプロパティ を持つ頂点が与えられた場合、可能なパスに沿ったすべての頂点がプロパティを含むようPに、頂点への最長パスを見つけるアルゴリズムを見つけたい (または書きたい) と思います。EallVEP
例 1
次のグラフがあるとします。(アスキーでの描画が下手なのはご容赦ください。)
+----+
+--------+P +--------+
| +----+ |
| V1 |
| |
| |
+--v--+ |
+----+P ++ |
| +-----++ +--v--+
| | +----+P |
| | | +-----+
+--v--+ +--v--+ |
|P +-+ +-+P | |
+-----+ | | +-----+ |
| | |
| | |
+v-v--+ |
V6 |P +---------+ |
+-----+ | |
| |
| |
| |
| |
+-v--v-+
V7 |P |
+---+--+
|
|
+---v--+
V8 |!P |
+------+
から始まり、可能なすべてのパスで常に保持されるV1最長パスは->です。他のパス、たとえば->は、常に有効であるという点で「有効」ですが、 ->が最も長いことに注意してください。PV1V7V1V6PV1V7
例 2
Pこの例は、が保持されないことを除いて、上記と同じV3です。
+----+
+--------+P +--------+
| +----+ |
| V1 |
| |
| |
+--v--+ |
+----+P ++ |
| +-----++ +--v--+
| | +----+!P | V3
| | | +-----+
+--v--+ +--v--+ |
|P +-+ +-+P | |
+-----+ | | +-----+ |
| | |
| | |
+v-v--+ |
V6 |P +---------+ |
+-----+ | |
| |
| |
| |
| |
+-v--v-+
V7 |P |
+---+--+
|
|
+---v--+
V8 |!P |
+------+
この場合、 から始まり、すべての可能なパスで常に保持されるV1最長パスは->です。パス->は有効ではありません。と の間にが保持されないパスがあるためです。PV1V6V1V7V1V7P
私の状況に関する追加メモ
- グラフは周期的である可能性があります。
- グラフは「小から中」のサイズで、おそらく 1000 個以下の頂点になります。
- 上記の例のように、グラフには必ずしも 1 つのルートと 1 つのリーフがあるとは限りません。
質問
そのようなパスを計算するための標準アルゴリズムはありますか?