区间(图论)算法解释

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
      }
    }
  }
}