激活节点和OR节点

Question

考虑有向图和节点和OR节点。只有当进入它的所有边都被激活时，才会激活和节点。如果激活了至少一个进入OR节点的边缘，则OR节点被激活。如何设计一个有效的算法来决定是否可以激活所有节点？我想过一些天真的算法，但它需要O(n^3)时间。我还假设没有边的顶点被初始化激活，我相信n^3不可能是一个有效的算法，并且有一些我忽略的方法。对问题可能有解决方案的域进行标记。

Answer 1

您可以对图进行预处理，以计算每个节点的内度。

将所有0级的节点添加到堆栈中，并准备一个数组A，其中包含每个节点的激活计数(最初等于0)。

然后执行以下伪代码

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)

这将访问每个边缘和每个节点最多一次，因此将具有线性复杂性。

当您完成过程时，访问包含一组已激活的节点。

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和节点之间的差异。

当此进程终止时，集合A包含所有已激活的节点。

运行时为O(V+E)，其中V为图中的节点数，E为边数。

Answer 3

这在O(n)中是可能的。这是一个可能的算法。

n节点总数

s已被激活的节点之和

a数组指示节点n是否已被激活。

c数组用于计数节点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);
        }
    }
}