区间(图论)算法解释

Question

我正在尝试计算图形中的间隔，我在维基百科上找到了该算法的数学描述：

http://en.wikipedia.org/wiki/Interval_（graph_theory）

   H = { n0 }                               // Initialize work list
   while H is not empty
       remove next h from H     
       create the interval I(h)
       I(h) += { h }
       while ∃n ∈ { succ(I(h)) — I(h) } such that pred(n) ⊆ I(h)
           I(h) += { n }
       while ∃n ∈ N such that n ∉ I(h) and    // find next headers
             ∃m ∈ pred(n) such that m ∈ I(h)
           H += n  

然而，这可能是非开发人员的代码的样子，因为它对我来说看起来像胡言乱语，这在 pesudo 代码中会是什么样子？我的最终实现将采用C++，并应用于控制流图数据结构，该结构具有每个节点的前置和后继边缘。

Answer 1

看起来维基百科代码是一阶逻辑; 伪代码如下所示，免责声明：我不熟悉这个算法，我只离开了 FOL"代码"

Set<Node> pred(Node n);
Set<Node> succ(Node n);
Set<Node> succ(Set<Node> interval) {
  Set<Node> retVal = new Set()
  // union of all successor edge sets for nodes in the interval
  for(Node n: interval) {
    retVal.addAll(succ(n))
  }
  // only return nodes that have predecessor edges in the interval
  for(Node n: retval) {
    if(interval.intersect(pred(n)).isEmpty()) {
      retVal.remove(n)
    }
  }
  return retVal
}
void main(Set<Node> N) { // N is the set of all nodes 
  Queue H = new Queue(N.first()) // the work queue
  while(!H.isEmpty()) {
    Node h = H.poll() // remove the first node from the queue
    Set<Node> I = new Set() // the interval
    I.add(h)
    for(Node ni : succ(I)) {
      I.add(ni) // or I.addAll(succ(I))
    }
    for(Node ni: N) {
      if(!I.intersect(pred(ni)).isEmpty()) {
        H.add(ni) // add nodes whose predecessors are in I to the work queue
      }
    }
  }
}