11

有向グラフでサイクルを検出するのに役立つ並行アルゴリズムを探しています。

シーケンシャルアルゴリズムが色付きのdfsを使用していることは知っていますが、マルチスレッド環境では失敗すると思います。それを説明するための有向グラフの一例：

A->（B、C）、B->（D）、D->（E）、C->（E）、E->（F）

                         A
                        / \
                       B   C
                       |   |
                       D   |
                        \ /
                         E
                         |
                         F

（上記が明確になることを願っています。グラフのエッジはすべて上から下にあります）

上記の有向グラフの場合、同時実行中に以下の実行が可能です。

（私が想定した配色スキームは、白-未訪問、灰色-dfsの実行が終了しておらず、黒-実行と訪問が終了しています）

スレッド1によるDfs（B）。これは最終的にEを灰色に着色し、dfs（E）を実行します（Fにつながります）。これが完了する前に、スレッド2はdfs（C）を実行します。Eが灰色であることを認識し、明らかにそうではないサイクルを報告します。

Tarjanのアルゴが循環検出にも使用できることを確認しましたが、マルチスレッド環境ではその実行が正しくないと思います。

誰かがこれについて私を助けてくれませんか？

ありがとう。

4

3 に答える 3

1

Ira が述べているように、各スレッドに独自の色を使用させます。

ただし、固定数のスレッドがある場合は、各色にビット マップを使用します。プロセッサがアトミック ビットのテストとセット (つまり x86 の BTST) をサポートしている限り、各スレッドが異なるビットをテストして設定するため、イベントをロックする必要はありません。

ビットが設定されている場合、アイテムはグレーで表示されます。

PS: より多くの色が必要な場合は、より多くのビットを使用できます。

于 2012-05-22T09:03:55.377 に答える
1

マルチスレッド サイクル検出の場合、DFS の代わりに Kahn アルゴリズム (トポロジカル ソート用) のバリアントを使用することをお勧めします。これは、次の事実を使用します。

1) 有向グラフが非巡回の場合、少なくとも 1 つの頂点に入力エッジがなく、少なくとも 1 つの頂点に出力エッジがない。

2) インエッジまたはアウトエッジのない頂点はサイクルに参加できません。それで

3) インエッジまたはアウトエッジのない頂点を削除すると、元のグラフと同じサイクルを持つ小さな有向グラフが残ります。

したがって、並列サイクル検出を行うには、次のことができます。

1) まず、並列 BFS を使用して、各頂点のイン次数とアウト次数を追跡するデータ構造を構築します。

2) 次に、並行して、入次数または出次数が 0 の頂点を削除します。頂点を削除すると、隣接するノードの入次数または出次数が減少することに注意してください。

3) 削除する頂点がなくなると、サイクルに関係するすべての頂点が残ります。何もない場合、元のグラフは非循環的でした。

並列 BFS (ステップ 1) と並列頂点削除 (ステップ 2) は、並列作業キューを使用して簡単に実行できます。ステップ 1 で、頂点を初めて見たときに、隣接する頂点を処理するタスクをキューに追加します。ステップ 2 で、頂点のイン次数またはアウト次数を 0 にデクリメントするときに、グラフから削除するタスクを追加します。

このアルゴリズムは、入次数が 0のノードまたは出次数が 0 のノードのみを削除しても同様に機能しますが、並列処理の機会が多少減少することに注意してください。

于 2016-07-11T14:10:58.487 に答える
0

サイクル検出の問題に対処する分散デッドロック検出アルゴリズムを簡単に見つけることができます。

分散型が厳密にはマルチスレッドではないことは理解していますが、それでもヒントが見つかるはずです。

編集：制限付きソリューションを追加しました。

于 2012-05-22T09:59:55.973 に答える