Interval (теория графов) алгоритм объяснения

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

Похоже, код википедии в логике первого порядка; псевдокод будет выглядеть следующую, оговорка: Я не знаком с этим алгоритмом и буду только прочь ВОЛП «код»

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