ANDノードとORノードの有効化

Question

ANDノードとORノードを持つ有向グラフを考えてみましょう。 ANDノードは、その中のすべてのエッジがアクティブになったときにのみアクティブになります。 ORノードは、その中の少なくとも1つのエッジがアクティブ化されている場合にアクティブになります。どのように効率的なアルゴリズムを設計すると、すべてのノードを有効にすることができるかどうかを決定する？私はいくつかの素朴なアルゴリズムを考えましたが、O（n^3）時間がかかります。私はまた、その中にエッジがない頂点が最初に活性化されると仮定しています。私はn^3が効率的なアルゴリズムではないと思っています。問題の解決に役立つドメインにタグを付ける

Answer 1

グラフを前処理して、各ノードのin-degreeを計算することができます。

度数0のすべてのノードをスタックに追加し、各ノード（最初は0に等しい）のアクティブ化カウントを含む配列Aを準備します。

は、その後、次の擬似コードに

visited = set(stack) 
while stack: 
    node = stack.pop() 
    for dest in node.neighbours(): 
     A[dest] += 1 
     if ((Type[dest]==AND and A[dest]==indegree[dest]) or 
      (Type[dest]==OR and A[dest]>0)): 
     if node not in visited: 
      visited.add(node) 
      stack.append(dest) 

を行うこれは、最高1回、各エッジと各ノードを訪問するので、線形複雑度を持つことになります。

このプロセスを終了すると、visitedにはアクティブ化されたノードのセットが含まれます。

Answer 2

すでにアクティブ化されたノードのセットA、ノードのキューQ、および各ノードのインエッジのカウンタCを維持します。エッジでカウントすることにより、

スタート：

for each n in nodes { 
    for each n2 adjacent to n { 
     C[n2] += 1 
    } 
} 

が続いていないで、エッジとノードとQを初期化：キューが空になるまで

for each n in nodes { 
    if C[n] == 0 { 
     add n to Q 
    } 
} 

は今、このプロセスを繰り返します。

take q from Q 
for each n adjacent to q { 
    if n is in A { continue } 
    if n is OR { 
     add n to A 
     add n to Q 
    } else { // n must be AND 
     C[n] -= 1 
     if C[n] is 0 { 
      add n to A 
      add n to Q 
     } 
    } 
} 

[ORノードとANDノードの違いに対応するトポロジカルソートの変形です] 。

このプロセスが終了すると、Aにはすべてのアクティブ化されたノードが含まれます。

ランタイムはO（V + E）です（Vはグラフのノード数、Eはエッジ数）。

Answer 3

O（n）でも可能です。可能なアルゴリズムは次のとおりです。

nノード

sノードnは、着信の数をカウントする

cアレイが活性化されているかどうかを示すために

aアレイを活性化されたノードの和の合計数ノードnのエッジ

受信エッジがない場合は、ノードを経由して伝達関数を呼び出します。 propagate(i);。

s == nの場合、すべてのノードがアクティブ化されています。

propagate関数の擬似コード：

function propagate(idx) { 
    if (a[idx]) // is node activated already 
     return; // return because node was already propagated 
    a[idx] = true; // activate 
    s++; // increase the number of activated nodes 
    for (var j = 0; j < outEdges[idx].length; j++) { // iterate through the outgoing edges 
     var idx2 = outEdges[idx][j]; // the node the edge is pointing to 
     if (isOrNode[idx2]) { 
      propagate(idx2); 
     } else { // AND node 
      c[idx2]++; // increase the count of incoming activated edges 
      if (inEdges[idx2].length == c[idx2]) // all incoming edges have been activated 
       propagate(idx2); 
     } 
    } 
}