強く接続された頂点のすべてのセットを見つける

Question

私は強連結成分のすべてのセットを見つけることを試みている有向グラフへの連結リストを持っています。誰も私に良い最悪の時間のアルゴリズム（サンプル擬似またはCコードは非常に感謝される）に向けて私を指摘することができます。

EDIT：強く接続されたコンポーネントを作成し、頂点を作成しないすべてのエッジのセットを見つけようとしています。下のグラフでは、強連結成分を作成するために2組の辺があることに注意してください。ただし、グラフ上の2つの辺のみが両方（a→bとb→c）に使用されます。アルゴリズムは、セット{a-> b、b-> c、c-> a}および{a-> b、b-> c、c-> b、b-> a}を生成することができます。

http://img521.imageshack.us/img521/8025/digraph.jpg

より多くの私の目標をクリアするのに役立ちます希望。

EDIT2：私は半完成の実装をしていますが、私が検索しているグラフも強く接続されていると動作しないことに気付きました。誰でもSCC内でSCCを見つける方法を知っていますか？

Answer 1

strongly connected componentsのウィキペディアページは3つのアルゴリズムを指していますが、それらはすべてウィキペディアでソースコードに直接翻訳するのに十分詳細に説明されています。その情報が不十分な場合は、正確に何が欠けているかを示す必要があります。

Answer 2

ウィキペディアのStrongly connected component定義には3つのアルゴリズムが推奨されています。私はTarjan'sと効率と実装の容易さの最高の組み合わせとして行くだろう。

私はwikipediaで擬似コードを取り、すべてのSCCのリストを保持するように変更しました。それは次のとおりです。

Input: Graph G = (V, E) 

List<Set> result = empty 
index = 0         // DFS node number counter 
S = empty         // An empty stack of nodes 
for all v in V do 
    if (v.index is undefined)     // Start a DFS at each node 
    tarjan(v, result)      // we haven't visited yet 

procedure tarjan(v, result) 
    v.index = index       // Set the depth index for v 
    v.lowlink = index        
    index = index + 1 
    S.push(v)         // Push v on the stack 
    for all (v, v2) in E do     // Consider successors of v 
    if (v2.index is undefined)    // Was successor v' visited? 
     tarjan(v2, result)     // Recurse 
     v.lowlink = min(v.lowlink, v2.lowlink) 
    else if (v2 is in S)     // Was successor v' in stack S? 
     v.lowlink = min(v.lowlink, v2.index) // v' is in stack but not the dfs tree 
    if (v.lowlink == v.index)    // Is v the root of an SCC? 
    set interconnected = empty 
    previous = v 
    repeat 
     v2 = S.pop         
     interconnected.add((previous,v2)) // record this edge 
     last = previous=v2 
    until (v2 == v) 
    result.add(interconnected) 

---

編集をさらに仕様に応じて。 アルゴリズムが頂点をスタックにプッシュしてから再びポップすることがわかりますか？これはおそらく、それぞれの連続したスタック要素がエッジによって前に接続されていることを知ることができるということを意味します。私はこれを反映するために上記の擬似コードを修正しましたが、試してみませんでした。

Answer 3

2回目の編集後でも、あなたの目標が実際に何であるかまだ分かりません。これは、用語の選択によって妨げられています。たいていの人は、SCCはすべてが互いに到達可能な頂点の最大集合であり、どのようなパスが発生するかは重要ではないということを意味します。

誰でもSCC内でSCCを見つける方法を知っていますか？

通常の定義では、SCCが最大であるため、SCC内にSCCというものはありません。

あなたは別のものを探しています：接続されたグラフから始め、あなたがよく特徴づけていない特定のエッジセットを見つけたいと思っています。私は強く思っていることは、あなたが望むものを明確な方法で特定すれば、アルゴリズムが落ちるということです。

私が最初に推測したのは、接続されたグラフに対して、各ペアを結ぶすべてのパスのすべての可能な組み合わせのエッジセットが必要なことでした。その場合は、これを行う簡単な方法は、各ペアについて、すべてのパスを見つけてすべての組み合わせを見つけ、重複を排除することです。しかし、この例では、すべてのエッジを使用することが可能であるため、リストに含まれているセットより多くのセットが生成されます。

エッジセットは、元の頂点をSCCのままにしておきます。この場合、元のエッジセットのpower setの各要素が候補になりますが、グラフがまだ接続されているが、まだ接続されているサブセットがないすべての候補が必要です。

これは、セットのこの格子を歩いてこの条件をチェックする簡単なアルゴリズムを提供します。グラフが接続されているかどうかをチェックするのは、エッジを削除または追加するのと同様に単純です。しかし、同様のグラフはほとんど同じ構造を持っているので、以前の問題からできることを再利用したいと思うでしょう。

助けることができるいくつかの参考文献：特にエッジや頂点についてのローカル情報をグラフのグローバル情報の接続点で

• Connectivity (graph theory)
• Menger's Theorem
• Max-flow min-cut theorem

。

---

開始グラフGには、頂点VとエッジEのセットがあり、強く接続されています。 目標は、Eからのエッジをすべて削除すると、グラフを複数のSCCに分割するような、すべての「最小」のエッジの集合E 'を出力することです。すべての可能なエッジセットを検索することでこれを行うことができます。

素直にこれがある：明らかに未接続のグラフは をテストされ、各グラフの接続性は、多くの何回もテストされます。

for E' in powerset(E): 
    if (V, E') strongly connected: 
     for e in E': 
      if (V, E' - e) strongly connected: 
       try next E' # Not minimal 
     add G' = (V, E') to list of minimal subsets. 

しかし、これは非常に無駄です。 可能性のあるエッジセット を、はるかに良い順に検索し、これらのエッジセットを格子状に並べることで、最初のものを取り除くことができます。各 エッジセットには、そのエッジセットから1つのエッジを引いた「直接の子」があります。 SCCではないグラフに入ると、 のいずれかをチェックする必要はありません。SCCでもかまいません。 を表現する最も簡単な方法は、グラフ検索です。深さの最初の検索は、多くの場合、より少ないメモリを使用するので、移動する方法は ですが、後で我々は横断の順序を使用するため、幅広い最初の 検索を選択します。 （深さが の場合、最初の検索でキューがスタックに変更されます）。

push starting node on queue 
while queue not empty: 
    pop node from queue 
    for c in suitable children, not on queue: 
     push c on queue 
    deal with node 

「ではないキューオン」の部分は、そうでない場合は、各ノードが 何回も訪問することができ、非常に重要です。スーパーセットのいずれかではないので

push E on queue 
while queue not empty: 
    pop E' from queue 
    if (V, E') strongly connected: 
     minimal = true 
     for e in E': 
      if (V, E' - e) strongly connected: 
       push E' - e on queue if not on queue 
       minimal = false   
     if minimal: 
      add G' = (V, E') to list of minimal subsets. 

今ではおそらく強く接続することはできませんすべてのedgesets、 をスキップ：これが私たちにアルゴリズムが変わります。欠点は、可能であれば が多くのスペースを使用できることです。ただし、それでもなお、 の接続性が繰り返し確認されます。しかし、キャッシュ情報があります。

check_or_add_cached_connected(E) 
push E on queue 
while queue not empty: 
    pop E' from queue 
    connected = cached (E') 
    if connected: 
     minimal = true 
     for e in E': 
      child_connected = check_or_add_cache(E' - e) 
      if child_connected: 
       push E' - e on queue if not on queue 
       minimal = false 
     if minimal: 
      add G' = (V, E') to list of minimal subsets. 
    remove E' from cache 

キャッシュが開始されたので、キャッシュできるようになりました。 エッジを削除するとグラフが破損し、サブグラフも破損します。 これは、グラフで「必要なエッジ」を追跡し、 をサブグラフに伝播できることを意味します。また、サブグラフのチェックを避けるために、これらの必須の エッジを確認することができます。

check_or_add_cached_connected(E) 
push E on queue 
while queue not empty: 
    pop E' from queue 
    (connected, required_edges) = cached (E') 
    if connected: 
     minimal = true 
     for e in E' and not in required_edges: 
      child_connected = check_or_add_cached_connected(E' - e) 
      if child_connected: 
       push E' - e on queue if not on queue 
       minimal = false 
      else: 
       add e to required_edges 
     if minimal: 
      add G' = (V, E') to list of minimal subsets. 
     else: 
      for e in E' and not in required_edges: 
       merge_cache(E' - e, required_edges) 
    remove E' from cache 

キャッシュやキューの構造を効率的に行うことができます使用する操作を確実にするための作業のビットを必要としますが、これはかなり簡単です。